なぜか素数判定をやるのにヒープソートがでてきたでござるの巻
今週末はSPOJのPRIC(http://www.spoj.pl/problems/PRIC/)をやってるのだが、なぜか素数判定にヒープソートを使うというわけの分からない実装ができてしまった。
まず、等差数列を素数で割ったあまりを考えると
| an | mod 3 | mod 5 | mod7 | mod 11 | mod 13 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 35 | 2 | 0 | 0 | 2 | 9 |
| 69 | 0 | 4 | 6 | 3 | 4 |
| 103 | 1 | 3 | 5 | 4 | 12 |
| 137 | 2 | 2 | 4 | 5 | 7 |
| 171 | 0 | 1 | 3 | 6 | 2 |
| 205 | 1 | 0 | 2 | 7 | 10 |
| 239 | 2 | 4 | 1 | 8 | 5 |
| 273 | 0 | 3 | 0 | 9 | 0 |
| 307 | 1 | 2 | 6 | 10 | 8 |
こんな感じに規則的に並ぶじゃん。当たり前だけど、ほとんどの素数pの列はp行ごとに0がでてくる。
だから試し割したい素数の数に対して、その素数周期のタイマーを走らせておけばタイマーが発火したらそこは合成数じゃん。
大量のタイマーを管理する簡単な方法は、発火時間の近い順にソートしたリストをもっておいて、一つ前のタイマーとの時間差を持っておく方法で、こうしておくと、1tickごとに変数を一個デクリメントして0かどうか判定するだけで、全てのタイマーのカウントダウンを行える。
大昔のLinuxカーネルのタイマーとかこんなだった。
というわけで、PRICでこれを使うと変数を一個デクリメントして0かどうかを見る。0だったら合成数。違ったら素数。エクスパイアしたタイマーは再開してタイマーリストの適切な場所に挿入する。これだけでいいじゃん。
でも、よく考えてみたら再開したタイマーをリストに挿入するのが遅そう→そうだヒープソートを使おう！
というわけで、ヒープソートを使ってタイマーリストを作ると何がうれしいかというと
- 結局、一番最初に発火するタイマーだけわかってれば、あとは線型に並んでる必要がないことを利用できる。完全にソートする必要はなくてヒープを組み立てるだけでよい。
- エクスパイアしたタイマーをすぐに正しい位置に戻せる
と思って実装してみたんだけど、というか、この方法は一番最初に思いついたけど面倒だから無視してたんだけど、
微妙に速くない。それなりに10位台にはなりそうなスピードではあるけれども…
