Pythonで素数判定

この記事では、Pythonで素数かどうかを判定する方法について解説します。効率的なアルゴリズムとサンプルコードを通して、素数判定を理解しましょう。

素数とは？

素数とは、1 と自分自身以外に正の約数を持たない 1 より大きい自然数のことです。例えば、2, 3, 5, 7, 11 などが素数です。

ナイーブな方法による素数判定

最も単純な素数判定方法は、2 から n-1 までのすべての整数で n を割ってみる方法です。割り切れるものがあれば、n は素数ではありません。

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

print(is_prime_naive(2))  # True
print(is_prime_naive(15)) # False
print(is_prime_naive(97)) # True

この方法はシンプルですが、n が大きくなると非常に非効率になります。

効率的な素数判定アルゴリズム (6k ± 1)

すべての素数は 6k ± 1 の形で表すことができます（ただし、例外として 2 と 3 は除きます）。この性質を利用して、判定範囲を絞り込み、効率化を図ることができます。

def is_prime_6k(n):
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

print(is_prime_6k(2))  # True
print(is_prime_6k(15)) # False
print(is_prime_6k(97)) # True

このアルゴリズムは、ナイーブな方法よりも効率的に素数判定を行うことができます。

効率的な素数判定アルゴリズム (エラトステネスの篩)

エラトステネスの篩は、ある範囲内のすべての素数を一度に求めるアルゴリズムです。素数判定だけでなく、素数のリストが必要な場合に非常に有効です。

def sieve_of_eratosthenes(limit):
    primes = [True] * (limit + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if primes[i]:
            for j in range(i * i, limit + 1, i):
                primes[j] = False
    return [i for i, is_prime in enumerate(primes) if is_prime]

primes = sieve_of_eratosthenes(100)
print(primes) # [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]

このアルゴリズムは、大量の素数を効率的に求めることができますが、単一の数の素数判定にはオーバヘッドが大きいため、単独の素数判定には向いていません。

サンプルコードと実行結果

上記の各アルゴリズムのサンプルコードと実行結果を示しました。それぞれのアルゴリズムの効率性の違いを確認してみてください。

注意点

非常に大きな数に対する素数判定は、どのアルゴリズムを用いても計算コストが高くなります。そのような場合は、確率的素数判定アルゴリズムなどを検討する必要があります。

入力値の妥当性チェックを行うこと
アルゴリズムの選択は、判定対象の数や必要とされる効率性によって異なる

PYTHON MEBY