Pythonで数値nがk個の素数の合計として表せるかどうかを判定するプログラム

ある整数 n と個数 k が与えられたとき、「n を k 個の素数の合計として表すことができるかどうか」を判定する問題を考えてみましょう。

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

解法のアプローチ

この問題を効率的に解くために、以下の手順に従います。

• n < 2×k の場合
  • False を返す（最小の素数は2なので、k個の素数の合計の最小値は 2×k になるため）
• k > 2 の場合
  • True を返す（任意の n ≥ 2k は k 個の素数の合計として必ず表現できることが知られているため）
• k = 2 の場合
  • n が偶数であれば True を返す（ゴールドバッハ予想により、4以上の偶数は2つの素数の和で表せるとされるため）
  • (n − 2) が素数であれば True を返す（n = (n−2) + 2 と表現できるため）
  • それ以外は False を返す
• k = 1 の場合
  • n 自体が素数であれば True を返す
• 上記以外は False を返す

実装例

それでは、実際のコードを見て理解を深めましょう。

def isPrime(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 isPrime(n-2):
         return True
      return False

   if isPrime(n):
      return True
   return False

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

入力

30, 3

出力

True

このように、素数判定関数 isPrime() と条件分岐を組み合わせることで、n が k 個の素数の合計として表現可能かどうかを簡単に判定できます。