プロジェクトオイラー問46 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046
Problem 46 「もうひとつのゴールドバッハの予想」 †
Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.
後に, この予想は誤りであることが分かった.
平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?

#include<stdio.h>

const int LIMIT=10000;
bool not_prime[LIMIT]={1,1,0};

int main(){
	for(int i=2;i*i<LIMIT;i+=1+(i&1)){
		if(not_prime[i]==true)continue;
		int start=4,add=2;
		
		if(i%2==1){
			start=i*3;
			add=i*2;
		}
		for(int j=start;j<LIMIT;j+=add){
			not_prime[j]=true;
 		}
	}
	for(int i=3;i<LIMIT;i+=2){
		if(not_prime[i]==true){
			bool hit=false;
			for(int j=1;j*j*2 < i;j++){
				if(not_prime[i-j*j*2]==false){
					hit=true;
					break;
				}
 			}
			if(hit==false){
			printf("ans=%d\n",i);
 				return 0;
			}
		}
	}
}