素数を判定する方法について、Pythonでどうやって実装するか

素数を判定する方法として以下のものが挙げられます。

1. 2からn-1までのすべての整数を順番に試して、nがそれらの整数で割り切れるかどうか確かめる簡単な方法があります。nがどれかの整数で割り切れる場合、nは素数ではありません。 この方法の時間計算量はO(n)です。

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

1. n の平方根以下の整数だけを調べればよいので、最適化されています。というのは、n が平方根より大きい整数で割り切れる場合、平方根より小さい整数でも割り切れます。同じように、n が平方根より小さい整数で割り切れない場合、平方根より大きい整数でも割り切れません。時間計算量は O(sqrt(n)) となります。

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

1. エラトステネスの篩とは、指定した範囲内の全素数を効率的に見つけるアルゴリズムです。具体的には、2から順に全ての数を調査し、2の倍数を非素数とマーキングし、次にまだマーキングされていない最小の数を探して素数とマーキングし、その倍数を非素数とマーキングする作業を、全ての数がマーキングされるまで繰り返します。このアルゴリズムの時間計算量はO(nloglogn)です。

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    return primes

状況に応じてこれら手法が選択的に利用できます。単に数が素数かどうかを判定する必要がある場合は、第1手法または2手法が利用できます。一定の範囲内の全ての素数を列挙する必要がある場合は、第3手法が利用できます。