Pythonで素数を判定する3つの方法を徹底解説【初心者向け】

このチュートリアルでは、Pythonを使って「ある数が素数かどうか」を判定するための、さまざまな方法を段階的に解説します。基本的な実装から計算量を抑えた最適化手法まで、コード例とともにわかりやすく紹介していくので、ぜひ最後まで読んでみてください。

方法1：基本的な素数判定アルゴリズム

まずは、もっともシンプルで一般的な素数判定の方法です。考え方は以下の通りです。

• 数値が1以下の場合は False を返す（素数ではない）
• 2から n-1 までのすべての整数で割り切れるかを確認し、1つでも割り切れる数があれば False を返す
• ループが最後まで終われば、約数は存在しないため True を返す

サンプルコード

# 素数判定関数
def is_prime(n):
    if n <= 1:
        return False
    else:
        for i in range(2, n):
            # 約数があるかチェック
            if n % i == 0:
                return False
        return True

print(f"Is 2 prime: {is_prime(2)}")
print(f"Is 4 prime: {is_prime(4)}")
print(f"Is 7 prime: {is_prime(7)}")

実行結果

上記のコードを実行すると、次のような出力が得られます。

Is 2 prime: True
Is 4 prime: False
Is 7 prime: True

この方法は直感的で理解しやすい反面、n が大きくなると判定回数が増えて処理に時間がかかるという欠点があります。

方法2：平方根まで調べて高速化する

次の方法では、判定範囲を n の平方根までに絞ることで、ループの回数を大幅に減らしています。ある数 n が約数を持つ場合、その約数のペアの一方は必ず √n 以下になるため、√n まで確認すれば十分だからです。

サンプルコード

import math

# 素数判定関数
def is_prime(n):
    if n <= 1:
        return False
    else:
        # n の平方根までループ
        for i in range(2, int(math.sqrt(n)) + 1):
            # 約数があるかチェック
            if n % i == 0:
                return False
        return True

print(f"Is 2 prime: {is_prime(2)}")
print(f"Is 4 prime: {is_prime(4)}")
print(f"Is 7 prime: {is_prime(7)}")

実行結果

Is 2 prime: True
Is 4 prime: False
Is 7 prime: True

方法1と比べて計算量が O(n) から O(√n) に改善されるため、大きな数を扱う際に効果的です。

方法3：偶数を除外してさらに高速化する

方法2では平方根までのすべての数を確認しましたが、よく考えてみると偶数は2以外すべて素数になりません。そこで、あらかじめ偶数を除外することで、さらに無駄な判定を減らすことができます。

サンプルコード

import math

# 素数判定関数
def is_prime(n):
    # 1以下の場合
    if n <= 1:
        return False
    # 2の場合
    elif n == 2:
        return True
    # 2より大きい偶数の場合
    elif n > 2 and n % 2 == 0:
        return False
    else:
        # 奇数のみを対象に、n の平方根までループ
        for i in range(3, int(math.sqrt(n)) + 1, 2):
            # 約数があるかチェック
            if n % i == 0:
                return False
        return True

print(f"Is 2 prime: {is_prime(2)}")
print(f"Is 4 prime: {is_prime(4)}")
print(f"Is 7 prime: {is_prime(7)}")

実行結果

Is 2 prime: True
Is 4 prime: False
Is 7 prime: True

range(3, ..., 2) とすることで、3から始まる奇数のみを順番にチェックしています。これにより、判定にかかる時間をさらに短縮できます。

まとめ

今回は、Pythonで素数を判定するための3つの方法を紹介しました。

• 方法1： シンプルだが遅い基本形
• 方法2： 平方根まで調べることで高速化
• 方法3： 偶数を除外してさらに効率化

小さな数ならどの方法でも問題ありませんが、扱う数が大きくなるほど最適化の効果は顕著になります。用途に応じて適切な方法を選んでみてください。このチュートリアルについて質問や不明点がある場合は、コメント欄でお気軽にお尋ねください。