【Python】エラトステネスの篩を実装する

エラトステネスの篩

素数を見つけるためのアルゴリズム。 素数の倍数を除外していき、全ての数値を走査して最後まで除外されなかった数値群が素数となる。

ja.wikipedia.org

実装

# n以内の素数をリストで返す
def sieve_of_eratosthenes(n):
    
    n += 1

    if n == 2: return [2]

    # キャッシュ
    cache = [True] * n

    for i in range(2, n + 1):
        # キャッシュにヒットしたら計算しない
        if not cache[i]: continue

        multiple = 2
        i_multiple = i * multiple

        while i_multiple < n:
            # iの倍数は素数ではないのでFalse
            cache[i_multiple] = False

            # 倍数をインクリメント
            multiple += 1
            i_multiple = i * multiple

    # 素数
    primes = []

    for index, predicate in enumerate(cache):
        if predicate: primes.append(index)
    
    # 0と1は素数に含まない
    return primes[2:]