素数判定のPythonメソッド

素数判定法として以下が挙げられます。

1. 暴力的判定方法：1よりその数未満の整数それぞれで割り切れるか判定する。割り切れる数があれば素数ではない、なければ素数である。この方法は、時間計算量はO(n)である。

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

1. 約数判定は√n以下の整数だけで行えばよい、なぜなら√nより大きな約数が存在するならば√n以下の約数も必ず存在するからである。この手法の時間計算量はO(√n)である。

import math

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

1. 素数を構成する、エラトステネスの篩方式は、まず1からnまでの全ての数を素数とする。次に2から√nまでの数で、2とその倍数を順に消していく。同様に3から√nまでの数で、3とその倍数を順に消していく。これで、残った数は素数となる。このアルゴリズムの時間計算量はO(nloglogn)である。

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

幾つかの素数の判定方法を挙げたが、効率は方法によって異なるので、用途に応じて適切な方法を選択する必要がある。