読者です 読者をやめる 読者になる 読者になる

AOJ 0185 - Goldbach’s Conjecture II

404 Not Found

コードゴルフ的解法で。

C (162 Byte)

o[1<<20],n,r;
main(i){
 for(;++i<999;)
  if(!o[i])
   for(r=i+i;r<1<<20;r+=i)
    o[r]=1;
 for(;scanf("%d",&n),n;printf("%d\n",r))
  for(i=1,r=0;++i<=n/2;)
   o[i]+o[n-i]||r++;
 exit(0);
}

 短さと速度を両立させた感じ。エラトステネスのふるいです。最初添字1000001まであったんだけど、求め方的に無駄だなって思って999999にした。あと、999ってとこも√1000000=1000だったんだけど1000に一番近い素数が997だから999にした。

 色々工夫凝らした結果がこれで、特に最初のmain(i){for(;++i<999;)らへんがんばった。main引数変数の性質で1で初期化され、前置インクリメントでforすることで2からループを回す。

 それでもまだ改善点とかありそうだけど疲れた。ちなみにこの問題試し割りなどで素数を求めるとTLEしてしまう。

 Submitしまくってたらコードサイズ変わらなくなった。サーバーに負荷かけてセンセンシャル!

追記(16:25)

 999999を1<<20に置き換えたら2byte縮まった。