エラトステネスの篩

エラトステネスの篩（ふるい）とは、

ある整数ｎ以下の全ての素数を見つけるための高速なアルゴリズムのこと。

アルゴリズム

1. ２からｎまでの整数をリストに入れる。
2. ２から順番にその倍数（その数自身は除く）をリストから削除していく。
3. ｎの平方根になれば終了。リストに残ったものが素数となる。

（例）ｎ＝１２

1. ２から１２までの整数を用意。

　[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

2. ２から順番にその倍数（その数自身は除く）を削除していく。

　①２の倍数をリストから削除

　[2, 3, 5, 7, 9, 11]

　②３の倍数をリストから削除

　[2, 3, 5, 7, 11]

3. １２の平方根に達したので終了。

ｎ＝１２以下の素数として[2, 3, 5, 7, 11]を得ることができた。

プログラム

pythonでのプログラムを書いてみる。

n = 12
# 1. ２から１２までの整数を用意。
# ここでは長さ１３のリストを用意し、インデックスが整数に対応している。
# 例えば、整数２はprimes[2]。
# リストの中身は素数ならば１、削除されれば０とする。
# つまり、２から１２までののリストを用意すると次のようになる。
# [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. ２から順番にその倍数を削除していく。
# ここでの削除は値を０にすることである。
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]