女性向けエンジニアスクール
3秒でわかる
2 から順に倍数を消していき、消し残った数を素数として得る古典的な手法。範囲内の素数をまとめて求めるときの定番になります。
もう少し詳しく
どういうものか
エラトステネスのふるいは、ある上限までの素数をまとめて列挙するアルゴリズムです。2 以上の整数を一覧にし、まだ消えていない最小の数を素数として確定させ、その倍数をすべて消す。これを繰り返すと、消し残った数だけが素数として残ります。
手順は下記のとおりです。
2 から n までの数を並べる
2 は素数 -> 4, 6, 8, ... を消す
3 は残っている -> 9, 12, 15, ... を消す
4 は消えている -> 飛ばす
5 は残っている -> 25, 30, ... を消す
sqrt(n) を超えたら終了。残った数がすべて素数なぜ必要か
1 つの数が素数かを調べるだけなら、割り算を平方根まで試せば十分です。しかし 100 万までの素数を全部欲しい場合、その判定を 100 万回繰り返すと重くなります。ふるいは割り算を一切せず、足し算による添字の移動だけで済むため、n log log n という計算量で全体が片付きます。素因数分解の前処理や、競技プログラミングでの数論問題では最初に置く道具です。
具体例
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
p = 2
while p * p <= n:
if is_prime[p]:
for multiple in range(p * p, n + 1, p):
is_prime[multiple] = False
p += 1
return [i for i, prime in enumerate(is_prime) if prime]
print(sieve(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]内側のループが p * 2 ではなく p * p から始まっている点が要点です。p より小さい素因数を持つ倍数は、その素因数の番のときに既に消えているため、重複して消す必要がありません。
つまずきやすいところ
配列の大きさを n にして is_prime[n] で範囲外エラーを出す例が多くあります。上限 n 自身を含めるので長さは n + 1 です。
0 と 1 を False にし忘れるのも定番です。どちらも素数ではありませんが、初期値のままだと結果に混ざります。
内側のループを while p <= n で回してしまうと、無駄が増えるうえ p * p を超えた範囲の判定が終わっているのに走り続けます。終了条件は p * p <= n です。
似た用語との違い
| 手法 | 用途 | 計算量の目安 |
|---|---|---|
| エラトステネスのふるい | n 以下の素数を全部出す | n log log n |
| 試し割り法 | 1 つの数が素数かを見る | sqrt(n) |
| ミラー・ラビン法 | 巨大な数の素数判定 | 確率的に高速 |
覚え方
「素数を探す」のではなく「素数でないものを消す」。発想を反転させたところがこの手法の全てです。
