(소수 + 2 × 제곱수) 로 나타내지 못하는 가장 작은 홀수 합성수는?

[eng][kor]

연산은 작은 홀수 합성수부터 시작하면 되고, 매 연산마다 소수가 들어간 계산을 해야 하므로 소수는 저장해놔야 할 것 같다. 그리고 하나의 연산 안에서 2제곱수 부분을 늘려가며 남은 부분이 소수인지 아닌지 판별하면 될 것 같고.

소수 소스는 역시 오일러 35번에서 푼 걸 가져다 쓴다.

/*
 	Problem 46 - Goldbach's other conjecture
*/

#include <iostream>
#include <ctime>
#include <cmath>
#include <map>

using namespace std;

std::map<unsigned long int, unsigned long int> primes;
bool isprime( unsigned long int n)
{
	if( n == 2) return true;

  std::map<unsigned long int,unsigned long int>::iterator 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) { return false; }
  }

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

unsigned long int twiceOfSquare( unsigned long int n)
{
	return 2*pow(n,2);
}

int main(int argc, char** argv)
{
	clock_t begin = clock();
	/* starting code */
	for(unsigned long int i=1;;i++)
	{
		unsigned long int n = 2*i+1;
		if (!isprime( n)) {
			cout << "n=" << n << endl;
			bool goldbach = false;

			unsigned long int s=1;
			while( true)
			{
				unsigned long int t = twiceOfSquare( s);
				if (t>=n) break;

				if( isprime( n-t)) {
					goldbach = true;
					break;
				}
				s++;
			}
			
			if( !goldbach) {
				cout << "goldbach false number = " << n << endl;
				break;
			}
		}
	}

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

위 생각대로 풀었고 답이 나왔다. 실행시간은 0.011 초.