C++에서 소수의 합으로 홀수 표현하기

이 문제에서는 홀수 N이 주어집니다. 우리의 임무는 소수의 합으로 홀수를 표현하는 것입니다.

숫자를 표현하는 동안 최대 3개의 소수가 있을 수 있습니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력: N =55

출력: 53 + 2

해결 방법:

홀수는 소수의 합으로 나타낼 수 있습니다. 이 소수를 고려하면 세 가지 경우가 있습니다.

사례 1: n이 소수이면 하나의 소수 n의 합으로 표시됩니다. .
사례 2: (n - 2)가 소수이면 두 소수 n-2와 2의 합으로 표현됩니다. .

사례 3: ( n - 3 )은 Goldbach의 추측 방법을 사용하여 두 소수의 합으로 나타낼 수 있는 짝수입니다. 여기서 숫자 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