Python

pythonでエラトステネスのふるい

nまでの素数を効率的に求めるエラトステネスのふるい手順をPythonコードで記載します。

nまでの素数を求める

素数とは

1より大きい自然数で1と自分自身以外に約数を持たない数。英語でPrime Number。

エラトステネスのふるい手順

1. 2～nまでの整数を順番に書き出す。
2. 書き出した数値の中から一番小さい数値を素数pとする。
   （既に素数として選ばれた数値、ふるい落とされた数値は除く）
3. 素数pを除くpの倍数を全て消去する（ふるい落とす）。
4. 手順2～3を素数pが\(\sqrt{n}\)を超えるまで繰り返す。残った数値がnまでの素数となる。

Pythonでエラトステネスのふるい

記載の手順にそって冗長的に書いたコードです。ふるい処理の途中経過を出力しています。

In [2]:

# nまでの素数（エラトステネスのふるい）

n = 100

A = list(range(2, n+1)) # 2～nまでの素数候補の集合リスト
sqrt_n = n ** (1 / 2) # √n

print('素数候補')
print(A)

idx = 0

while True:
    p = A[idx] # リストidx番目の素数p
    if p > sqrt_n: break # 素数pが√nを超えたら、ふるい終了

    print('p={}の倍数をふるい落とす'.format(p))
    check_numbers = A[idx+1:] # 素数を除くふるい対象
    for check_number in check_numbers:
        if check_number % p == 0: # 素数pの倍数を集合リストから削除
            A.remove(check_number)
    print(A)
    idx += 1

print('{0}までの素数 計{1}個'.format(n, len(A)))
print(A)

素数候補
[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, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
p=2の倍数をふるい落とす
[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]
p=3の倍数をふるい落とす
[2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97]
p=5の倍数をふるい落とす
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97]
p=7の倍数をふるい落とす
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
100までの素数 計25個
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

スポンサーリンク