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

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

エラトステネスの篩（ふるい）は、効率よく 素数 を求めることができるアルゴリズムです。

指定された範囲の中から２で割り切れる数、３で割り切れる数、・・・・と割り切れる数を順に除外する方法です。

これを繰り返すと最後には 素数 だけが残ることになります。

[Google Colaboratory]

import math

def get_prime(n):
    if n <= 1:                  # 1以下の場合
        return []               # 空リストを返す
    prime = [2]                 # 素数リストを 2 だけで作成
    limit = int(math.sqrt(n))   # 検索する上限を設定(nの平方根)

    data = [i for i in range(3, n, 2)]      # 奇数のリストを作成
    while limit >= data[0]:                 # 上限≧奇数の先頭の場合
        prime.append(data[0])               # 素数リストに奇数の先頭を追加
        # 奇数リストのうち、先頭の数で割り切れないものでリストを作成
        data = [j for j in data if j % data[0] != 0]

    return prime + data       # 素数リストと奇数のリストを合わせて返す

print(get_prime(100))         # 100までの素数を求める

[実行結果]

[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]

高速に素数を求めることができました。