エラトステネスの篩(ふるい)とは、
ある整数n以下の全ての素数を見つけるための高速なアルゴリズムのこと。
アルゴリズム
(例)n=12
1. 2から12までの整数を用意。
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
2. 2から順番にその倍数(その数自身は除く)を削除していく。
①2の倍数をリストから削除
[2, 3, 5, 7, 9, 11]
②3の倍数をリストから削除
[2, 3, 5, 7, 11]
3. 12の平方根に達したので終了。
n=12以下の素数として[2, 3, 5, 7, 11]を得ることができた。
プログラム
pythonでのプログラムを書いてみる。
n = 12 # 1. 2から12までの整数を用意。 # ここでは長さ13のリストを用意し、インデックスが整数に対応している。 # 例えば、整数2はprimes[2]。 # リストの中身は素数ならば1、削除されれば0とする。 # つまり、2から12までののリストを用意すると次のようになる。 # [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] primes = [0, 0] + [1] * (n-1) # 平方根 root = int(pow(12, 0.5))+1 # 2. 2から順番にその倍数を削除していく。 # ここでの削除は値を0にすることである。 for i in range(2, root): if primes[i]: for j in range(i*i, n+1, i): primes[j] = 0 print(primes) # [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0] primes = [i for i in range(n+1) if primes[i]] print(primes) # [2, 3, 5, 7, 11]