Pythonプログラムでの素数判定 - シンプル実装やエラトステネスの篩（ふるい）

素数とは、1と自分自身以外に約数を持たない正の整数のことです。Pythonを使って、素数判定プログラムを作成することができます。以下に、いくつかの異なる実装方法を示します。

方法1: 単純な素数判定

最も基本的な素数判定アルゴリズムは、ある数nが素数かどうかを調べるために、2からn-1までの数でnを割り切れるかどうかを確認する方法です。

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

この実装は非常にシンプルで理解しやすく、数が小さい場合には素早く動作します。しかし、非常に大きな数の場合には遅くなります。また、この方法はnが素数である場合にも、2からn-1までのすべての数を確認する必要があるため、非常に効率が悪いです。

方法2: 繰り返しの回数を減らした素数判定

上記のアルゴリズムを少し改良することで、繰り返しの回数を減らすことができます。具体的には、nの平方根以下のすべての数でnを割り切るかどうかを確認するだけです。

import math

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

この実装は前の方法よりも効率的で、nが素数の場合には2からn-1までのすべての数を確認する必要がなくなります。しかし、依然として非常に大きな数に対しては遅くなります。

方法3: エラトステネスの篩

エラトステネスの篩とは、ある範囲内のすべての素数を一度に見つけるためのアルゴリズムです。具体的には、2からnまでのすべての数をリストに入れ、2から始めて、2の倍数、3の倍数、4の倍数...というように、その数自体を除く倍数をすべて削除することで、素数だけが残るようにします。

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

この実装は、ある数nまでの素数を全て一度に見つけることができる非常に効率的なアルゴリズムです。エラトステネスの篩のアルゴリズムは、nが小さい場合でも大きい場合でも同じ速度で動作します。ただし、この実装は、2からnまでのすべての数をリストに入れるため、非常に大きな数の場合にはメモリの使用量が非常に大きくなる可能性があります。

pydocument.hatenablog.com