프로젝트 오일러 60
projecteuler, cppPrime pair sets 문제..
아 진짜 드디어 풀었다. 너무 안 풀려서 원칙을 깨고 다음 문제로 넘어가려 했는데, 자꾸 이 문제가 생각나서 다시 들여다봤고 결국 답이 나왔다.
코드가 문제를 푸는 알고리즘은 다음과 같다.
1) 일단 소수를 구한다.
2) 소수를 자릿수로 두개로 쪼갰을때, 쪼갠 두 수가 소수가 되는지 확인한다. 그 역도 확인한다.
3) 한편 프로그램은 소수쌍을 관리하는 pairmap을 갖고 있고, 2)를 확인할 때마다 소수 pairmap 을 업데이트한다.
4) pairmap은 대략 다음과 같이 생겼다.
key, pair 후보 배열
[3] : a1, a2, a3 …(a는 3과 페어가 될 수 있는 소수)
[7] : b1, b2, b3 …
[9] : c1, c2, c3 …
…
5) pairmap을 돌며 4개이상 갖고 있는 배열만 검사를 시작한다. 각 pair 후보를 키로 한 후보배열을 검사한다. 처음에 뽑은 5 pair들이 모두 그 후보배열에 있는지 검사한다.
근데 여기서 후보배열에 없다고 pair 가 불가능하냐 하면 그건 아니다. -_-;; 왜냐하면 내가 2)에서 소수 페어를 추출해낸 방식이, 큰 소수를 쪼개서 거기서 소수 페어 재료가 나왔는지 확인해본 방식이기 때문이다. 여기서는 소수 페어 재료를 갖고 큰 소수가 될 수 있는 경우도 있다. 따라서 소수맵에 소수 페어가 없더라도 두 소수의 합이 소수가 되는지 한번 더 체크해본다. (이 과정을 풀이에 넣기까지 시간이 정말 많이 들어갔다.)
실행시간은 360초 정도로 꽤 걸린다. 하지만 나는 그저 문제를 풀었다는 것에 만족한다. ^^;;
/*
Problem 60 - Prime pair sets
*/
#include <iostream>
#include <ctime>
#include <vector>
#include <map>
#include <cmath>
#include <string.h>
#include <algorithm>
using namespace std;
std::map<unsigned long int,unsigned long int> primes;
std::map<unsigned long int,unsigned long int> notprimes;
bool isprime( unsigned long int n)
{
if( n == 1) return false;
if( n == 2) return true;
std::map<unsigned long int,unsigned long int>::iterator it;
it = notprimes.find(n); if( it != notprimes.end()) { return false; }
it = primes.find(n); if( it != primes.end()) { return true; }
unsigned long int s = sqrt( n) + 1;
for(unsigned long int i=s; i>1; i--)
{
if (n%i ==0) {
notprimes.insert( std::map<unsigned long int, unsigned long int>::value_type( n, n));
return false;
}
}
primes.insert( std::map<unsigned long int,unsigned long int>::value_type( n, n));
return true;
}
std::map<unsigned long int, vector<unsigned long int>> pairmap;
class PrimePair
{
private :
unsigned long int me;
unsigned long int a;
unsigned long int b;
bool is;
public:
PrimePair(unsigned long int _me, unsigned long int _a, unsigned long int _b) {
me = _me;
is = true;
if (_a < _b) {
a = _a;
b = _b;
} else {
a = _b;
b = _a;
}
std::map<unsigned long int, vector<unsigned long int>>::iterator it;
// insert a map
it = pairmap.find(a);
if ( it != pairmap.end()) {
if( std::find(it->second.begin(), it->second.end(), b) == it->second.end()) {
it->second.push_back( b);
}
} else {
std::vector<unsigned long int> v; v.push_back(b);
pairmap.emplace( a, v);
}
// insert b map
it = pairmap.find(b);
if ( it != pairmap.end()) {
if( std::find(it->second.begin(), it->second.end(), a) == it->second.end()) {
it->second.push_back( a);
}
} else {
std::vector<unsigned long int> v; v.push_back(a);
pairmap.emplace( b, v);
}
}
unsigned long int getme() { return me; }
unsigned long int geta() { return a; }
unsigned long int getb() { return b; }
bool getis() { return is; }
void print() { cout << me << ":" << a << "," << b; }
};
std::vector<PrimePair> getPrimePairs( unsigned long int p)
{
std::vector<PrimePair> r;
char buf[1024] = {0,};
sprintf( buf, "%ld", p);
int len = strlen( buf);
for(int i=0; i<len; i++)
{
char b1[1024] = {0,}; char b2[1024] = {0,};
strncpy( b1, buf, i+1);
strncpy( b2, buf+i+1, len-i);
if( b1[0] == '0' || b2[0] == '0' | b2[0] == 0) continue;
unsigned long int n1 = atol(b1); unsigned long int n2 = atol(b2);
if( isprime(n1) && isprime(n2)) {
char buf2[1024] = {0,};
sprintf( buf2, "%ld%ld", n2, n1);
if( isprime( atol( buf2))) {
PrimePair newp(p, n1, n2);
r.push_back( newp);
}
}
}
return r;
}
long int minsum = -1;
void combination( std::vector<unsigned long int> src, int choose, int nowi, std::vector<unsigned long int> result)
{
if( choose <= 0) {
// DONE
unsigned long int sum = 0;
for(int i=0; i< result.size(); i++)
{
sum += result[i];
}
if( minsum == -1 || sum < minsum) {
minsum = sum;
for(int i=0; i<result.size(); i++)
{
cout << result[i] << " ";
}
cout << " minsum : " << minsum << endl;
}
return;
}
for(int i=nowi; i<src.size(); i++)
{
std::vector<unsigned long int> r(result);
bool keepgo = true;
for(unsigned long int j=0; j<r.size(); j++)
{
std::map<unsigned long int, vector<unsigned long int>>::iterator it;
it = pairmap.find(r[j]);
if( it == pairmap.end()) { keepgo = false; break; }
if( std::find(it->second.begin(), it->second.end(), src[i]) == it->second.end()) {
char str[1024] = {0,};
sprintf( str, "%ld%ld", src[i], r[j]);
if( isprime( atol(str))) {
char str2[1024] = {0,};
sprintf( str2, "%ld%ld", r[j], src[i]);
if( isprime( atol(str2))) {
keepgo = true;
} else {
keepgo = false; break;
}
} else {
keepgo = false; break;
}
}
}
if( keepgo) {
// insert a map
r.push_back( src[i]);
if( src[i] == 0) { cout << "i=" << i << " src[i]=" << src[i] << endl; }
combination( src, choose-1, i+1, r);
}
}
return;
}
#define PICK 5
#define MAX 400000
int main(int argc, char** argv)
{
clock_t begin = clock();
/* starting code */
cout << "MAX=" << MAX << endl;
std::vector<PrimePair> pps;
for(unsigned long int i=3; i<MAX; i++)
{
if( isprime( i)) {
std::vector<PrimePair> pp = getPrimePairs(i);
pps.insert( pps.end(), pp.begin(), pp.end());
}
}
cout << "primes.size())=" << primes.size() << endl;
cout << "pps.size())=" << pps.size() << endl;
cout << "pairmap.size()=" << pairmap.size() << endl;
for( auto it = pairmap.begin(); it != pairmap.end(); it++) {
std::vector<unsigned long int> r;
r.push_back( it->first);
combination( it->second, PICK-1, 0, r);
}
cout << "answer minsum = " << minsum << endl;
/* end of code */
clock_t end = clock();
std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
return 0;
}