素数を計算する

チームラボさんのブログにC言語の練習にちょうど良さそうな課題があったのでやってみた。
1000万個目の素数を超高速に出力せよ
エラトステネスの篩自体はそんなにむずかしくなかったけど、ちょっと大きめの配列を宣言したらスタックがあふれた・・・のでmallocでメモリを確保する。ポインタ操作になれないのでポインタのアドレスを書き換えて変な動作になったりしてド素人な感じです。mallocで宣言してもintの配列だと1000万個目の素数を弾きだすためには数百Mくらいメモリが必要なので、32bitのintを32個のbit配列として扱うようにした。BitSetっていうらしい。俺ってアッタマいーいとか思ってたらまあ誰でも思いつくことのようで・・・
そんなこんなで3時間どころか5時間くらいかかって9秒くらいでした。

最初ReleaseじゃなくてDebugで実行して計測してしまい、19秒とかだったので俺は馬鹿でC言語なんて使う資格ないんじゃないかとか、チームラボのエンジニアは化け物か！とか思ったけど結論としては俺はマヌケということだった。無駄はまだまだあるけど面倒になってきたのでこれで終わりに使用。
チームラボさんとこの計測用マシンのスペックがわからんけど、Cで実装すればとりあえず3位以内になるんじゃなかろうか。