SPOJ-PRIC 素数判定 １位奪還！

やりました。
SPOJ-PRICの１位を、取りました。
2009年8月にハンガリーのRobert Gerbiczさんが１位を取ってから１年と５ヶ月ぶりに、日本が奪還したことになります。
アルゴリズム的には、前回の日記の時から何も変わっていません。
　
SPOJ PRIC Ranking
http://www.spoj.pl/ranks/PRIC/
　
あの後、各小素数ごとにD^{-1}をかけて現在位置を求める処理をmulなしで実装することに成功しましたが、速度が一切改善しなかったため、実はボトルネックが別の場所にあったことに気が付きます。
（私がボトルネックの箇所を間違えるのは稀です）
　
33Mの結果表に直接エラトステネスを適用すると、ページフォルトが起きまくって使い物にならないのは誰もが真っ先に気付くことで、そのため、一旦作業領域上でエラトステネスの篩を実行し、一区切りついた所で結果を転写しております。
　
ここでボトルネックになっていたのは、以下の２点でした。
　
・小さな素数（３とか）の倍数の塗り潰し
・作業領域から結果領域への転写
　
そのため、小さな素数である3と7について、特別な対策を取りました。（5は、X法に使われているXの素因数であったため、まとめ試し割りで除外されています）
　
3と7の合成数は21周期なので、21個まとめて転写するようにしました。
この21個のうち9個は、3の倍数または7の倍数であるため、最初から転写を免れます。
そのため、エラトステネスの篩を行う際、3と7については篩を行わなくて良いことになりました。
これら２つの事柄の両方が速度アップに結びついたことと、まとめforループが若干速度アップに繋がり、１位に浮上しました。
　
とりあえず嬉しいんですけど、１位が取れたそのこと自体よりも、生活に集中できることが一番嬉しいです。
　
今回素数判定に着手した大晦日から現在までだと、１０日間。
最初にSPOJ-PRIC(素数判定)に取り組んだ2008年1月7日からだと、実に３年間かけての１位です。
その３年間、素数判定のことが頭の片隅から消えない日はありませんでした。
これで今日からは新しいことに取り組めるというものです。
　
p.s.
そういえば、素数のことを【塗り残したタイル】と表現しているのは、Googleで検索した範囲だと、日本中では私一人の様です。
これは、エラトステネスの篩プログラムの動く様子が、タイルを塗っている様に見えて、塗らなかったタイルが素数となることに由来します。
　
Wikipediaのエラトステネスの篩の右側の動画のイメージです。
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
　
いやまぁ、なんというか。
フェルマーテストを使っていた時も、試し割りしている時も、X法上のエラトステネスの篩を使ってる時も、
脳内では常にタイルが塗られ、何が塗り残されるのかを考えながらだったので、
【塗り残したタイル】という表現は、非常にしっくり来るし、気に入っております。