1.ショートコーディングC[素数列]
今回は「素数列」のショートコードを書いてみましょう。
まずはそこそこ速いコードを
以下に、使い古された普通のCコードを書きます。
#include <stdio.h> #define N 100 int main(void){ int primes[N]; int i=1,n=3; int isPrime; int j; primes[0]=2; while(i<N){ isPrime=1; for(j=0;primes[j]*primes[j]<=n;j++){ if(n%primes[j]==0){ isPrime=0; break; } } if(isPrime==1){ primes[i]=n; i++; } n++; } for(j=0;j<N;j++){ printf("%d\n",primes[j]); } }
このコードは、作った素数列から次の素数を作って素数列に加えるということを繰り返して素数列を生み出しています。分かりやすい上にそこそこ速さも出ます。普通に組むならこれでよいでしょう*1。
ただ、このコードはアルゴリズムが複雑な分少し長くなってしまいますので、ショートコーディングには向かないアルゴリズムです。ですのでばっさり切り捨てて、速さを犠牲にしても短くなるものを考えましょう。
愚直に組む
以下に、もっとも素朴に素数の定義に基づいて組まれたコードを示します。
#include <stdio.h> int main(void){ int i,j,isPrime; for(i=2;;i++){ isPrime=1; for(j=2;j<i;j++){ if(i%j!=0) continue; isPrime=0; break; } if(isPrime==1){ printf("%d\n",i); } } }
ここでは、より短いプログラムを書くことと、どれだけアルゴリズムを犠牲にして短く書いているかを分かりやすく示すために無限ループにしてあります。
このソースではtimeoutが5秒で、71341まで出力されました。
短くしてみる
さて、いよいよショートコーディングを始めましょう。
とりあえず何も考えずにここまではやってみました。
// インデントや改行などを除いて72B j;main(i,p){ for(;i++;p=p?printf("%d\n",i):1) for(j=1;++j<i;p=(i%j)?p:0); }
アルゴリズムとしては、調べている数の素因数が見つかっても検索を終了しないようにしたので効率はかなり落ちています。同じ条件で20201まで出力されました。
解説としては、
- Cではインクルードはいらない、型宣言を省略するとint型に、グローバル変数は初期化しないと0になる
- main()の括弧の中で初期化すると1になる
- for(A;B;C)D;はA->B->D->Cの順で実行される
- printf関数の戻り値は出力した文字数になる
などを利用しています。
さらに短くしてみる
上でかなり短くはなりましたが、さらに短くすることが可能です。
// インデントや改行を除いて71B j;main(i,p){ for(j=1;++j<i;p=(i%j)?p:0); main(++i,p?printf("%d\n",i):1); }
まさに1バイトを削る戦いになってきました(笑) このコードでは、for文を消すためにmain再帰を用いています。main再帰は、for文におけるiのようなインデックスを表す変数への代入文を削るのに効果的です。実際、上のコードでも"p="を削って(ただしmainは4文字なのでその分1文字増えてしまいます)、71Bまで圧縮することができています。
アルゴリズムは少し変わりましたが、結局やはり2重ループを組んでいるだけなので上と同じく20201まで出力されました。
備考
私の貧弱な脳みそではこれ以上短いコードは思いつかなかったのでもし思いついた方がいらっしゃれば遠慮なく言っていただきたいです。
また、このコードは無限ループを組んでいるのでローカルで実行すると停止しません。ご注意ください。
個人的にはmain再帰なんて久しぶりに使ったので上手く動いてくれて安心しました。
追記(2012/7/5更新)
2個上のプログラムをいじっていたらさらに短くすることができました。
// インデントや改行を除いて67B j;main(i,p){ for(;p=j=i++;p&&printf("%d\n",i)) for(;j-1;p*=i%j-->0); }
pはi%jが0かどうかだけ判定しているので、上のように書いても同じになります*2。
そして更にここからpを消去することも出来ました。
// インデントや改行を除いて55B j;main(i){ for(;j=i++;j||printf("%d\n",i)) for(;i%j--;); }
変数が減ると格段に短くなりましたね<">*3
