Pythonで素数を2つの素数の和として表現できるか判定する方法

素数 n が与えられたとき、それを2つの素数 x と y の和(n = x + y)として表現できるかどうかを判定する問題です。

例えば、n = 19 の場合、19 = 17 + 2 と表現できるため、出力は True になります。

アルゴリズムの考え方

この問題には重要な数学的な性質があります。n が奇数の素数である場合、その和が奇数になる2つの素数の組み合わせでは、必ず片方が偶数になります。偶数の素数は 2 だけ なので、結局「n − 2 が素数かどうか」を確認すればよいことになります。

解決の手順

• 素数判定用の関数 isPrime() を定義します
• number が 1 以下の場合は False を返します
• number が 2 の場合は True を返します
• number が偶数の場合は False を返します
• 3 から √number + 1 の整数部分まで、2 ずつ増やしながらループし、number が i で割り切れる場合は False を返します
• いずれにも該当しなければ True を返します
• メイン処理では、isPrime(number) と isPrime(number - 2) がどちらも True なら True を返し、そうでなければ False を返します

それでは、実際の実装を見てみましょう。

実装例

from math import sqrt
def isPrime(number):
    if number <= 1:
        return False
    if number == 2:
        return True
    if number % 2 == 0:
        return False
    for i in range(3, int(sqrt(number))+1, 2):
        if number%i == 0:
            return False
    return True
def solve(number):
    if isPrime(number) and isPrime(number - 2):
        return True
    else:
        return False
n = 19
print(solve(n))

入力

19

出力

True

計算量について

このアルゴリズムの素数判定は、√n までの奇数のみを試すため、時間計算量は O(√n) となります。大きな数に対しても効率的に動作するのが特徴です。