Project Euler 46

Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2
後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数を答えよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046

#include <iostream>
#include <deque>

using namespace std;

//素数を max まで計算する
deque<bool> p;
void calc_prime(const int max){
	for(int i=0 ; i<max+1 ; i++){
		p.push_back(true);
	}
	p[0] = false;
	p[1] = false;

	double myEnd = sqrt(double(max));
	for(int i=2 ; i < myEnd ; i++){
		for(int j=2 ; i*j<=max ; j++){
			p[i*j] = false;
		}
	}
}

int main(){
	const int pmax=100000;
	calc_prime(pmax);

	int k=0;
	bool isGoldbach=false;

	for(int i=3 ; i<pmax ; i+=2){
		if(p[i]){
			cout << i << endl;
			continue;
		}

		isGoldbach = false;

		for(int j=1 ; ; j++){
			k = i - 2*j*j;

			if(k<0) break;

			if(p[k]){
				cout << i << " = " << k << "+ 2*" << j << "^2" << endl;
				isGoldbach = true;
				break;
			}
		}

		if(!isGoldbach){
			cout << endl << i << endl;
			break;
		}
	}
}