Pythonで素数を判定しよう！（基礎編＋）

こんにちは。学びの探求者です。

前回、基礎編では、素数の判定を「エラトステネスのふるい」を手動でやる方法とPythonを使って「平方根（√n）までの範囲で割り切れるかをチェックする」という方法をご紹介しました。

今回は、「エラトステネスのふるい」を手動でやった通りにPythonコードを書いてみましょう。

エラトステネスのふるいとは？（おさらい）

エラトステネスのふるいは、指定した範囲内の素数を効率よく見つける方法です。

1. 2を素数とし、それ以外の偶数をすべて消す。

2. 3を素数とし、それ以外の3の倍数を消す。

3. 5を素数とし、それ以外の5の倍数を消す。

4. 7を素数とし、それ以外の7の倍数を消す。

5. 11を素数とし・・・

では、これを手動でやった通りにPythonコードを書いて実行してみましょう。

コード

# エラトステネスのふるいを手動でやった通りに実行する
def intuitive_sieve(limit):
    numbers = list(range(2, limit + 1))  # 2からlimitまでのリスト

    # 偶数を除去（ただし2は例外）
    primes = [num for num in numbers if num == 2 or num % 2 != 0]

    # 次に3の倍数を除去（ただし3は例外）
    primes = [num for num in primes if num == 3 or num % 3 != 0]

    # 次に5の倍数を除去（ただし5は例外）
    primes = [num for num in primes if num == 5 or num % 5 != 0]
    
    # 次に7の倍数を除去（ただし7は例外）
    primes = [num for num in primes if num == 7 or num % 7 != 0]

    # 次に11の倍数を除去（ただし11は例外）
    primes = [num for num in primes if num == 11 or num % 11 != 0]
    
    # 残りの数をふるいにかける
    for num in range(13, int(limit ** 0.5) + 1, 2):
        primes = [p for p in primes if p == num or p % num != 0]

    return primes

# 例として、1から100までの素数を見つける
limit = 100
print(f"エラトステネスのふるいを手動でやった通りに実行する方法で見つけた素数: {intuitive_sieve(limit)}")

実行結果

エラトステネスのふるいを手動でやった通りに実行する方法で見つけた素数: [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]

まとめ

エラトステネスのふるいは、素数を効率よく見つけるための基本的な方法です。
今回紹介したふるい方は、手動での感覚をプログラムに落とし込んだもので、より直感的に理解しやすい方法です。
ただし、今回の方法では素数13以降は「基礎編」でご紹介した方法を補完的に使用しています。

次回は、上級編として 実務的な素数判定方法 をテーマに、セキュリティや大きな数値の素数探索といった実際に役立つ方法をご紹介します。

引き続きお楽しみに！