Pythonで2つの数の平方差が素数かどうかを判定する方法

2つの整数 x と y が与えられたとき、それぞれの2乗（正方形の面積とみなせます）の差が素数であるかどうかを判定する問題を考えてみましょう。

たとえば、x = 7、y = 6 の場合を考えます。このとき面積の差は 7² − 6² = 49 − 36 = 13 となり、13 は素数なので答えは True になります。

解法のポイント：因数分解の性質を利用する

単純に差を計算してから素数判定をする方法もありますが、数学的な性質を使うともっとスマートに解けます。2つの数の平方差は、次のように因数分解できます。

x² − y² = (x + y)(x − y)

素数は 1 とその数自身でしか割り切れないため、この積が素数になるのは「一方の因数が 1」の場合だけです。つまり、次の条件が両方満たされれば、平方差は必ず素数になります。

• (x − y) が 1 である
• (x + y) が素数である

アルゴリズムの手順

1. (x + y) が素数かどうかを判定する
2. (x − y) が 1 と等しいかどうかを確認する
3. 両方の条件を満たせば True を返し、そうでなければ False を返す

Pythonでの実装例

def is_prime(num):
    if num <= 1:
        return False
    if num <= 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i = i + 6
    return True

def solve(x, y):
    if is_prime(x + y) and x - y == 1:
        return True
    else:
        return False

x, y = 7, 6
print(solve(x, y))

入力

7, 6

出力

True

コードの解説

is_prime() 関数は、「6k ± 1」の性質を利用した効率的な素数判定関数です。まず 2 と 3 の倍数を除外し、その後 6 ずつ増やしながら候補を絞り込むことで、√num までの範囲だけで判定を完了できます。

solve() 関数では、前述の数学的性質に基づき、「x − y が 1」かつ「x + y が素数」という条件をチェックしています。このアプローチなら、実際に平方差を計算することなく、大きな数でも高速に素数かどうかを判定できるのが大きなメリットです。