優先順位つきキューを用いたエラトステネスの篩の変形

Algorithm

Haskellでエラトステネスの篩 - 簡潔なQ
上の記事に出てくる「優先順位つきキューを用いたエラトステネスの篩の変形」が C++ で書かれたコードを読んでもよく分からなかったので本人に尋ねてみた所，そもそも優先順位つきキュー自体がよく分かっていないことが判明し，それも含めて解説してもらった．
Sieve of Eratosthenes using a priority queue · GitHub
それでとりあえず分かった気になっていたのだけど，なんかひっかかるなあという感じになったので少し考えてみたら割と単純な話だった:

  1. i の初期値は素数 2 である．
  2. キューには i を越える最小の偶数 (素数 2 の倍数) が必ず含まれている．
  3. キューから pop した値を x としたとき 1 ≦ x - i ≦ 2 である．つまり i と x は隣り同士，または奇数 q を挟む形になっている．
  4. i と x が隣り同士で且つ i が偶数の場合，x は奇数である．このとき x は 2 以外で i 未満の素数 p の倍数である．従って i も x も素数ではないので，i に x + 1 を代入し，キューに x + 2p (x + p は偶数であるため既にキュー内に存在する) を追加する．
  5. i と x が奇数 q を挟む場合，q は素数．なぜなら，i 未満の素数において i を越える最小の倍数を y とすると x ≦ y が成り立ち q ≠ y となるからである．i に x を代入，キューに q^2 を追加して処理を続ける．
  6. (4.), (5.) より i は奇数になり得ないことに注意．

ちなみに 4. の

i 未満の素数において i を越える最小の倍数を y とすると x ≦ y が成り立ち

は

// 該当部分を抜き出したコード
int p = i+1;
pq.push(make_pair(-p*p, p));
pq.push(make_pair(-x-q, q));
i = x;

から分かる．