Pythonで素数かどうかを判定する方法

素数は、暗号技術をはじめとする多くのアプリケーションで中心的な役割を果たしています。そのため、さまざまな場面でPythonプログラムを使って素数を判定できることは重要なスキルとなります。素数とは、1とその数自身以外に約数を持たない数のことです。この記事では、与えられた数が素数かどうかを判定するPythonプログラムを、基本的な手法から最適化された手法まで段階的に紹介します。

基本的なアプローチ

ある数が素数かどうかを判定するには、以下の手順で処理を進めます。

• まず入力された数が正の数かどうかを確認します。素数になり得るのは正の整数だけだからです。

• 2から「その数より1小さい数」までの範囲にあるすべての整数で割ってみます。

• この範囲内のどれかの数で割り切れた（余りが0になった）場合は、その数は素数ではありません。

サンプルコード

x = 23
if x > 1:
    for n in range(2, x):
        if (x % n) == 0:
            print(x, "is not prime")
            print(n, "times", x // n, "is", x)
            break
    else:
        print(x, "is a prime number")
else:
    print(x, "is not prime number")

実行結果

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

23 is a prime number

6i±1の形を利用した効率的な判定

3より大きいすべての素数は「6i±1」の形で表せるという性質があります（iは1以上の整数）。これは、6i・6i+2・6i+4が必ず偶数になり、6i+3は必ず3の倍数になるためです。この性質を利用すると、2と3での割り算を先にチェックした後、実際に試すべき除数を6ずつ増やしながら「i」と「i+2」の2つだけに絞り込むことができます。さらに、試し割りは対象の数の平方根まで確認すれば十分です（それ以上大きな約数が存在するなら、対応する小さな約数が必ず見つかるためです）。

サンプルコード

def CheckPrime(n):
    # 2と3の場合をチェック
    if (n <= 1):
        return False
    if (n <= 3):
        return True
    # 2または3の倍数なら素数ではない
    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 = i + 6
    return True

# 入力値のチェック
if (CheckPrime(31)):
    print("true")
else:
    print("false")

if (CheckPrime(25)):
    print("true")
else:
    print("false")

実行結果

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

true
false