エラトステネスの篩: 素数をまとめて見つけよう
エラトステネスの篩は、素数ではない数をふるい落として、素数だけを残す方法です。
「2の倍数を消す、3の倍数を消す、5の倍数を消す」と進めていくと、最後に素数が残ります。
ルール
- 2から調べ始める
- 素数を見つけたら、その倍数を消す
- 次に残っている数へ進む
- 最後に残った数が素数になる
図で見る
30までの数で見ると、「残す数」と「消す数」が表のように変化します。
| 手順 | ふるいにかける数 | 数の表 |
|---|---|---|
| 最初 | まだ何も消していない | 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
| 1回目 | 2を残して、2の倍数を消す | 2 3 11 21 |
| 2回目 | 3を残して、3の倍数を消す | 2 3 11 |
| 3回目 | 5を残して、5の倍数を消す | 2 3 11 |
| 完成 | 消されずに残った数が素数 | 2 3 5 7 11 13 17 19 23 29 |
コピペ用コード
def sieve_of_eratosthenes(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = False
is_prime[1] = False
for number in range(2, int(limit ** 0.5) + 1):
if is_prime[number]:
for multiple in range(number * number, limit + 1, number):
is_prime[multiple] = False
primes = []
for number in range(limit + 1):
if is_prime[number]:
primes.append(number)
return primes
print(sieve_of_eratosthenes(30))
AOJで挑戦してみよう！
範囲内の素数をまとめて扱う問題で、エラトステネスの篩を使ってみよう。