【Python】nがk個の素数の和として表せるかどうかを判定する方法

問題の概要

2つの整数 n と k が与えられたとき、「n を k 個の素数の和として表すことができるか」を判定するプログラムを考えます。

例えば、入力が n = 30、k = 3 の場合、出力は True になります。これは、30 が 2 + 11 + 17 という3つの素数の和で表せるためです。

解法のアルゴリズム

この問題は、次の手順に従って判定できます。

• n < k × 2 の場合:False を返します。最小の素数は 2 なので、k 個の素数の和は必ず 2k 以上になります。したがって、n が 2k 未満であれば表現は不可能です。
• k > 2 の場合:True を返します。n が 2k 以上であれば、偶数・奇数どちらの場合でも適切な素数の組み合わせに分解できるためです(ゴールドバッハ予想に基づく考え方)。
• k = 2 の場合:
  • n が偶数であれば True を返します(4以上の偶数は2つの素数の和で表せるとされています)
  • (n − 2) が素数であれば True を返します(例:n = 9 → 2 + 7)
  • それ以外は False を返します
• n 自身が素数の場合:True を返します(k = 1 のケースに相当します)
• 上記以外:False を返します

Pythonでの実装例

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

def check_prime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def solve(n, k):
    if n < k*2:
        return False
    if k > 2:
        return True
    if k == 2:
        if n % 2 == 0:
            return True
        if check_prime(n-2):
            return True
        return False
    if check_prime(n):
        return True
    return False

n = 30
k = 3
print(solve(n, k))

コードの解説

check_prime 関数:引数 num が素数かどうかを判定する補助関数です。1 より大きい数について、2 から num − 1 までのすべての整数で順に割り算を試し、割り切れる数がひとつもなければ True(素数である)を返します。

solve 関数:メインとなる判定ロジックです。まず n と k の大小関係で表現の可否を絞り込み、k = 2 の場合は偶数判定と素数判定を組み合わせて答えを導きます。

入力

n = 30, k = 3

出力

True

このように、n = 30 は 2 + 11 + 17 と3つの素数の和で表せるため、プログラムは True を出力します。