素数野郎

SPOJもそのうち参戦しようと思ってたら、先日から素数判定の問題がちょっと流行ってそうなのでやってみました。
http://www.spoj.pl/problems/PRIC/
とりあえず、Miller-Rabinくらいしか知らないので普通にやってみると、最初は時間ギリギリで5,000,000個程度でした。ちょっと工夫したら13,000,000個。限界っぽいので多少のチューニングが必要な気がしましたが、仕事であまり時間が無いので、手元のgccで最適化コンパイルした後アセンブリ埋め込みで酷すぎる手抜きですが、これでも微妙に速度アップです。
http://www.spoj.pl/ranks/PRIC/
とりあえずTOP20入り(18位)したので良しとします。真面目にインラインアセンブリ書くと、どこまでイケるんでしょうね。私は頑張ってもせいぜい20,000,000個くらいかなーと思います。最大でも32bitの素数なので、32bitの範囲に特化した規則性とかがあるような気がするようなしないような。

上から3人くらいは全然違うアルゴリズムだと思いますが、サッパリわかりません。素数野郎は是非是非挑戦してくだされ。