エラトステネスの篩とは？
エラトステネスの篩(Sieve of Eratosthenes)は、2からN以下の全ての素数を一度に素早く見つける古典アルゴリズムです。数を1つずつ素数判定する代わりに、素数を見つけるたびにその倍数を全て消して合成数を取り除きます。
核心の一行: 「素数の倍数は素数ではない」。 小さい数から走査して倍数を消していくと、最後まで残った数が素数です。
動作原理
ステップ1. 2からNまで全てを「素数候補」(真偽値配列true)として表示します。
ステップ2. p = 2 から始めます。p がまだ候補なら、p の倍数 p², p²+p, p²+2p, ... を全て「素数でない」と消します。
ステップ3. p を1ずつ増やして繰り返します。p が √N を超えたら止めます — それより大きい合成数は既に小さい素数が消しています。
ステップ4. 最後まで真で残った数がN以下の全素数です。
AlgoNoteの可視化は、素数が決まるたびにその倍数が格子から順に消える様子をステップごとに示します。
なぜp²から消すのか？
p の倍数のうち p より小さい係数を持つもの(2p, 3p, ..., (p-1)p)は、既により小さい素数(2, 3, …)が消しています。 だから新たに消す最初の倍数は p × p = p² からで十分です。この小さな最適化が無駄な反復を大きく減らします。
同様に p > √N なら p² > N なので消す倍数が範囲内になく、止めてよいのです。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(N log log N) |
| 空間 | O(N) |
ほぼ線形に近い速度で、数百万までの素数を一瞬で求めます。
例で追ってみる
N = 20:
- •p=2: 4, 6, 8, …, 20 を消す
- •p=3: 9, 12, 15, 18 を消す
- •p=4: 既に消済み(スキップ)
- •p=5: 5 > √20 ≈ 4.47 → 停止
- •残り: 2, 3, 5, 7, 11, 13, 17, 19 → 全て素数
よくあるミス
- •2pから消す: 間違いではないが
p²から始めるより非効率です。 - •境界のオフバイワン:
p ≤ √Nまたはp*p ≤ Nの条件を正確に書きます。 - •1の扱い: 1は素数でないので最初から候補から除外します。
AlgoNoteで直接確認しましょう
素数が1つ決まるたびにその倍数が格子から消え、最後に素数だけ残る過程をAlgoNoteでステップごとに確認できます。