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

素数判定の基本的な考え方

ここで紹介する方法の原理は、与えられた数を3からその平方根までのすべての整数で順に割っていくというものです。ある数の平方根は、その数が持ちうる約数の中で最大の候補となる値です。したがって、平方根を超える数については、割り切れるかどうかを確認する必要はありません。

この関数は、2で割り切れる数や2未満の数に対しては False を返します。それ以外の数については、組み込み関数 all() を使い、平方根以下のいずれかの数で割り切れる場合には False（素数ではない）、どの数でも割り切れない場合には True（素数である）を返します。

サンプルコード

def is_prime(a):
    if a < 2:
        return False
    elif a != 2 and a % 2 == 0:
        return False
    else:
        return all(a % i for i in range(3, int(a**0.5) + 1))

num = int(input('enter a number'))
if is_prime(num) == True:
    print("{} is a prime number".format(num))
else:
    print("{} is not a prime number".format(num))

実行結果

上記プログラムの実行例は以下の通りです。

enter a number24
24 is not a prime number
enter a number47
47 is a prime number

ポイントの解説

このアルゴリズムのポイントは、判定範囲を「2から対象の数まで」ではなく「3から平方根まで」に限定している点です。これにより、計算量が大幅に削減され、大きな数でも高速に素数判定が行えます。

• 2未満の数（0や1など）は定義上素数ではないため、即座に False を返します。
• 2以外の偶数は必ず2で割り切れるため、素数ではありません。
• int(a**0.5) で平方根の整数部分を求め、そこまでの奇数についてのみ割り切れるかを検証します。