프로젝트 오일러 46
projecteuler, cpp연산은 작은 홀수 합성수부터 시작하면 되고, 매 연산마다 소수가 들어간 계산을 해야 하므로 소수는 저장해놔야 할 것 같다. 그리고 하나의 연산 안에서 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 초.