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; }