エラトステネスの篩

久々の更新です。

http://dev.team-lab.com/?itemid=207
こんな記事を見つけたので、挑戦してみました。
1000万番目の素数を出来るだけ早く出力する課題です。

素数を求める方法として有名なのが、エラトステネスの篩です。
ある範囲の自然数の数列を用意して、２の倍数のものを取り除く、次は３の倍数を、次は５、というようにして、合成数（約数が１と自身の値以外に存在する数）を取り除いていく方法です。
Wikipediaに分かりやすいgifアニメがあったので、イメージがつかみにくい人は、そちらを見ると良いかと思います。

エラトステネスの篩は、求めたい範囲が広くなれば広くなるほど、計算量がどんどん増えていきます。
今回は 10^7番目の素数を求めたいので、結構な範囲になります。（1.8*10^8ぐらい）


とりあえずC++で実装してみました。
char配列を2億個ぐらい用意して、要素の添字を、その要素の値としました。
あとは単純にforループを回して、2の倍数、3の倍数の要素にフラグを立てていくだけのプログラムでテスト。

そこそこ動くけど、何十秒もかかってる。
さっきの記事をもう一回見たところ、１位の人は1.4秒で出力してる！！！

改良の余地はたくさんあるらしいので、いろいろ試してみました。
最終的なコードがこれ。
https://gist.github.com/nekosan/a956c2794796750280ec

何を改良したかはコードから察して欲しい。（気力がないし、ぐぐると結構いろいろ出てきました）
配列からあらかじめ２の倍数のものを抜いたり、ループの回し方を変えたりしました。

最終的には、出力時間を0.9秒まで縮めることができました。（CPUはIntel Core i7 2.2GHz）
もうちょっと改良すれば縮められそうですが、疲れたので一区切りつけました。


単純に興味があってコードを書き始めましたが、結構勉強になりました。
演算子の処理時間とかを考えないといけないコードを最近書いてなかったので、いい復習になった気がします。

次もプログラミング関連の投稿になると思います。
そろそろ自分のHPぐらい持ってみたいものです。VPSとか借りようかな。