PKU 2909 Goldbach's Conjecture
http://poj.org/problem?id=2909
偶数nが与えられる。この数字を二つの素数の和で表す方法は何通りあるかを求める問題。
難しい問題は解けないので、ひたすら解け残っている簡単な問題をハイエナ。
bool pr[(1<<15)+1]; int npr[100000]; int num; main(){ pr[0]=pr[1]=1; for(int i=2;i<=1<<15;i++){ if(pr[i])continue; for(int j=i*2;j<=1<<15;j+=i)pr[j]=true; } set<int> spr; rep(i,(1<<15)+1)if(!pr[i])spr.insert(npr[num++]=i); int n; while(cin>>n,n){ int ans=0; for(int i=0;npr[i]*2<=n;i++){ if(spr.count(n-npr[i])){ ++ans; } } cout<<ans<<endl; } }