0185-Goldbach's Conjecture II

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0185
篩で全素数をリストアップ
nまでのすべての素数に対して加算してnになる素数があるかを調べる。

#define PRIMEMAX 1000001
//この数値未満の素数をすべて求めます

bool GetedPrime=false; //すでに素数を求めたかどうか
char Prime[PRIMEMAX];//0なら素数、1なら素数ではない
int PrimeList[PRIMEMAX];
int PrimeCount;
void EratosthenesSieve(){
	if(GetedPrime==true) return;
	int NeedCount=(int)sqrt(PRIMEMAX)+1;
	Prime[0]=1;
	Prime[1]=1;
	//2の倍数は素数ではない
	Prime[2]=0;
	for(int i=2;i<NeedCount;i++){
		if(Prime[i]==0){
			for(int j=i*2;j<PRIMEMAX;j+=i)
				Prime[j]=1;
		}
	}
	for(int i=2;i<PRIMEMAX;i++){
		if(Prime[i]==0) PrimeList[PrimeCount++]=i;
	}
	GetedPrime=true;
}
int main(int argc,char *argv[]){
	EratosthenesSieve();
	int n;

	while(1){
		scanf("%d",&n);
		if(n==0) break;
		int t=0;
		for(int i=1;PrimeList[i]<=n/2;i++){
			if(Prime[n-PrimeList[i]]==0) {
				t++;
			}
		}
		printf("%d\n",t);
		fflush(stdout);
	}
	return 0;
}