Sieve of Eratosthenes using a priority queue

gistfile1.txt

[10/07/14 15:51:49] qnighy/Acike: 最も有名な優先順位つきキューの実装は
[10/07/14 15:51:55] qnighy/Acike: 2分ヒープによるもので
[10/07/14 15:52:15] qnighy/Acike: 完全2分木の配列表現を用いる
[10/07/14 15:52:23] qnighy/Acike: 完全2分木の配列表現というのは、
[10/07/14 15:52:38] qnighy/Acike: まず、0番目の要素は使わない(ダミーとして使うなど)。
[10/07/14 15:52:43] qnighy/Acike: 根は1番目。
[10/07/14 15:52:59] qnighy/Acike: ある頂点nの親はn/2(切り捨て)。
[10/07/14 15:53:09] qnighy/Acike: ある頂点nの子はn*2とn*2+1。
[10/07/14 15:53:33] qnighy/Acike: で、完全二分木がヒープ条件を満たすとは
[10/07/14 15:53:49] qnighy/Acike: 根以外のどの頂点についても、その頂点より親のほうが大きい
[10/07/14 15:53:59] qnighy/Acike: よって根は最大
[10/07/14 15:54:51] qnighy/Acike: 削除の操作をするときは、とりあえず根を削除して、ヒープ条件を満たすように修正する。
[10/07/14 15:56:00] qnighy/Acike: 追加するときも同様。
[10/07/14 15:56:07] qnighy/Acike: そんな感じ。
[10/07/14 15:56:10] qnighy/Acike: ------------------------------
[10/07/14 15:56:24] qnighy/Acike: で、優先順位つきキューを使った素数生成なんだけど
[10/07/14 15:57:02] qnighy/Acike: 「この値はpの倍数だから篩いたい」という希望を優先順位つきキューに突っこんどく
[10/07/14 15:57:15] qnighy/Acike: で、最小を取りだす。
[10/07/14 15:58:00] qnighy/Acike: 10を篩った後に12を篩った場合は11が素数、というようにわかる。
[10/07/14 15:58:13] qnighy/Acike: で、例えば、12を篩ったとすると
[10/07/14 15:58:22] qnighy/Acike: 12を篩うのは
[10/07/14 15:58:37] qnighy/Acike: 「12は3の倍数だから篩いたい」「12は2の倍数だから篩いたい」の2つだから
[10/07/14 15:58:41] qnighy/Acike: これを処理したら、次に
[10/07/14 15:58:54] qnighy/Acike: 「15は3の倍数だから篩いたい」「14は2の倍数だから篩いたい」の2つを
[10/07/14 15:59:01] qnighy/Acike: 優先順位つきキューに突っこむ。
[10/07/14 15:59:05] qnighy/Acike: といった流れ。
[10/07/14 16:13:01] qnighy/Acike: 優先度は普通に篩いたい数字
[10/07/14 16:13:18] qnighy/Acike: 「nはpの倍数だから篩いたい」の集合をもつんだけど
[10/07/14 16:13:26] qnighy/Acike: 当然nが小さいものから取得したいから
[10/07/14 16:13:32] qnighy/Acike: 優先順位つきキューを使う