Pythonで素数列挙

素数列挙

ある与えられた自然数N以下の素数を列挙する関数を作ります。
使うアルゴリズムはエラトステネスの篩です。(参考ページ: エラトステネスのふるいとその計算量 | 高校数学の美しい物語)

from math import sqrt, ceil

def era_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))                            
    primes = [ n for n in range(N+1) if temp[n] ]
    return primes

7行目で「素数iを見つけた時に、i+iからi個間隔で数字を篩落とす」操作をしています。

素数判定

上記のエラトステネスの篩を使って素数判定をする関数を作ります。
プログラムの内容は上記のものと同じです。

from math import sqrt, ceil

def is_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))
    if not temp[N]:
        return False
    return True

Nが素数ならばTrueを、そうでないならばFalseを返します。