1백만 이하의 소수 중 가장 길게 연속되는 소수의 합으로 표현되는 수는?

[eng][kor]

정공법으로 풀기 쉽지 않아 보인다. 어떤 소수를 소수 체인의 합으로 나타낼 수 있는지, 만약 있다면 체인의 길이는 몇 개인지..를 구하는 함수를 작성하는 것은 쉽지 않다. 대신 오일러 문제 39번에서의 역발상처럼 풀었다. 소수를 소수 체인으로 표현할 수 있는지 고민하지 말고, 소수 체인의 합이 소수인지 따져보는 것이다.


1부터 백만 사이에 있는 소수를 모두 n개의 소수를 가진 체인으로 만든다. 여기서 n-1 개로 이루어진 부분 체인을 꺼낸다. 이 부분 체인을 이루는 소수들의 합이 백만 이하이면서 소수이면, 바로 이 합이 답이다. n-1 체인에서 답을 못 구하면 체인의 길이를 줄여 나간다.

실행시간 48.179초.(길긴 하군)

/*
	 Problem 50 - Consecutive prime sum 
 */
#include <iostream>
#include <ctime>
#include <map>
#include <cmath>
#include <vector>

using namespace std;

std::map<int,int> primes;
bool isprime( int n)
{
	if( n == 2) return true;
	std::map<int,int>::iterator it = primes.find(n);
	if( it != primes.end()) { return true; }

	int s = sqrt( n) + 1;
	for(int i=s; i>1; i--)
	{
		if (n%i ==0) { return false; }
	}

	primes.insert( std::map<int,int>::value_type( n, n));
	return true;
}


int main(int argc, char** argv)
{
	clock_t begin = clock();

	/* starting code */ 
	std::vector<int> pList;
	for(int i=2; i<1000000; i++)
	{
		if( isprime(i)) {
			pList.push_back( i);
		}
	}

	std::map<int,int>::iterator it;
	int chainLength = pList.size();
	while( chainLength >= 1) {
		cout << "max chain length :" << chainLength << endl;
		for(int i=pList.size()-1; i>=chainLength; i--)
		{
			unsigned long int sum = 0;
			for(int j=i; j>=i-chainLength; j--)
			{
				sum += pList[j];
				if( sum > 1000000) { break;}
			}
			if (sum < 1000000) {
				it = primes.find(sum);
				if( it != primes.end()) { 
					cout << "found answer = " << sum << " i=" << i << " pList[i]=" << pList[i] << endl;
					goto done;
				}
			}
		}
		chainLength--;
	}

done:
	/* end of code */
	clock_t end = clock();
	std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
	return 0;
}