素数判定

ずいぶん久しぶりになってしまいました。いくつか書いておきたい文章もあったのですが、推敲するのが面倒で書きっぱなしになっていました。10月ごろにマシンが壊れて、代替マシンも壊してしまって、いろいろと大変でありました。CF-W4GからCF-W7Bに変えてみましたが、カタログスペックに反してなんだかとてもバッテリーが持たなくなったような気がします。

さて、ごく一部でチャレンジされていた問題、
http://www.spoj.pl/ranks/PRIC/
に最近かなり時間を吸い取られていたのですが、ようやく終幕を迎えられそうです。

問題は、v[i]=(1+1234567890*i)%0x80000000 なる数列の先頭33333333個について素数かどうかを判定するのにかかる時間を競うというもの。

当初はミラーラビンを高速化しながらどろどろとやっていたのですが、今日の昼間にぽこっと思いついたアイデア一発で終わってしまいました。昨日までの苦労は相当なる時間の浪費でした。線形な最適化をやっていないので、最適化の余地は2,3割は残っていると思いますが、もうたぶんそこまでやる気は出ないと思います。分かったことは、こんな小さな数の素数判定なんて、どうにでもなるということです。アルゴリズムはもう少ししたら改めて書こうと思います。