素数判定のアルゴリズムとエラトステネスの篩

数論において、素数は非常に重要な役割を果たします。素数とは、1と自分自身以外の整数で割り切れない自然数のことです。この教材では、素数判定のアルゴリズムとエラトステネスの篩（ふるい）を用いて素数を効率的に見つける方法を学びます。

素数判定のアルゴリズム

最も基本的な素数判定のアルゴリズムは、数が素数かどうかを判定するために、その数の平方根までの整数で割り切れるかどうかを確認する方法です。この方法では、次のステップを踏みます。

1. 数が2未満の場合、素数ではない。
2. 2であれば素数。
3. 2以外の偶数であれば素数ではない。
4. 3からその数の平方根までの奇数で割り切れるかを確認する。

以下は、このアルゴリズムをPythonで実装したサンプルコードです。

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

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

# テスト
for number in range(1, 21):
    if is_prime(number):
        print(f"{number} は素数です。")
    else:
        print(f"{number} は素数ではありません。")

コード解説

• is_prime(n) 関数は、引数 n が素数かどうかを判定します。
• 最初に、n が2未満であれば素数ではないと判断し、2であれば素数であると返します。
• 次に、2以外の偶数は素数ではないため、その場合は False を返します。
• それ以外の場合、3から n の平方根までの奇数で割り切れるかを確認します。割り切れる場合は素数ではないと判断し、最終的に素数であれば True を返します。

エラトステネスの篩

エラトステネスの篩は、指定した範囲内の素数を効率的に見つけるためのアルゴリズムです。このアルゴリズムでは、次の手順を実行します。

1. 2から指定した数 n までのすべての整数をリストに追加します。
2. リストの最初の数を素数とし、その倍数をリストから削除します。
3. 次の未削除の数を素数とし、その倍数を削除します。
4. これをリストが空になるまで繰り返します。

以下は、エラトステネスの篩を実装したPythonのコードです。

def sieve_of_eratosthenes(n):
    primes = []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0と1は素数ではない

    for p in range(2, n + 1):
        if is_prime[p]:
            primes.append(p)
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False

    return primes

# テスト
n = 50
prime_numbers = sieve_of_eratosthenes(n)
print(f"{n}までの素数: {prime_numbers}")

コード解説

• sieve_of_eratosthenes(n) 関数は、引数 n までの素数をリストとして返します。
• is_prime リストを作成し、すべての数を素数として初期化します（0と1は素数ではないため、False に設定）。
• ループを使って、未削除の数を見つけ、その数を素数としてリストに追加し、その倍数を削除します。
• 最終的に、素数のリストを返します。

まとめ

この教材では、素数判定のアルゴリズムとエラトステネスの篩を学びました。これらのアルゴリズムは、数学やコンピュータサイエンスの多くの分野で基盤となる知識です。これらを活用して、より複雑な問題に挑戦してみてください。