C++で奇数を素数の和として表現する方法｜ゴールドバッハ予想を活用したアルゴリズム

この問題では、ある奇数Nが与えられます。求められているのは、その奇数を素数の和として表現することです。

ただし、表現に使用できる素数は最大で3つまでという制約があります。

問題を理解するための具体例

入力： N = 55

出力： 53 + 2

解法アプローチ

奇数は素数の和として表現できます。使用する素数の個数に着目すると、この問題は次の3つのケースに分けて考えることができます。

ケース1： n自体が素数である場合 → 1つの素数 n のみで表現できます。
ケース2： (n − 2) が素数である場合 → 2つの素数 2 と (n − 2) の和として表現できます。

ケース3： 上記のいずれにも当てはまらない場合 → まず3を引き、残りの (n − 3) は偶数になります。ここでゴールドバッハ予想の考え方を利用し、ある数Aが素数であり、かつ {(n − 3) − A} も素数であれば、その組み合わせを出力します。

ゴールドバッハ予想とは「4以上のすべての偶数は2つの素数の和として表現できる」という有名な予想で、この性質を利用すれば偶数を確実に2つの素数へ分解できます。

解法の動作を示すプログラム

サンプルコード

#include <iostream>
using namespace std;

bool isPrime(int x)
{
   if (x == 0 || x == 1)
      return false;
   for (int i = 2; i * i <= x; ++i)
      if (x % i == 0)
         return false;
   return true;
}

void primeAsSumofPrime(int n) {
   
   if (isPrime(n))
      cout<<n;
   else if (isPrime(n - 2))
      cout<<"2 "<<"+ "<<(n - 2);
   else{
      cout<<"3 "<<"+ ";
      n -= 3;
      for (int i = 0; i < n; i++) {
         if (isPrime(i) && isPrime(n - i)) {
            cout<<i<<" + "<<(n - i);
            break;
         }
      }
   }
}

int main() {
   
   int n = 561;
   cout<<"The number "<<n<<" expressed as sum of primes is ";
   primeAsSumofPrime(n);
   return 0;
}

出力：

The number 561 expressed as sum of primes is 3 + 11 + 547