C++で素数の合計として奇数を表現する

この問題では、奇数Nが与えられます。私たちのタスクは、素数の合計として奇数を表現することです。

数を表現している間、最大3つの素数が存在する可能性があります。

問題を理解するために例を見てみましょう

入力： N =55

出力： 53 + 2

ソリューションアプローチ：

奇数は素数の合計として表すことができます。これらの素数を考慮に入れると、3つのケースがあります。

ケース1： nが素数の場合、1つの素数の合計として表されます n 。
ケース2： （n-2）が素数の場合、2つの素数n-2と2の合計として表されます。 。

ケース3： （n-3）は偶数であり、ゴールドバッハの予想法を使用して2つの素数の合計として表すことができます。この方法では、数Aが素数であり、数{（n-3）-A}も素数であるかどうかを確認します。印刷してください。

ソリューションの動作を説明するプログラム

例

#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