用 C++ 将奇数表示为质数之和

在这个问题中，我们给定一个奇数 N。我们的任务是 *将奇数表示为质数之和*。

表示该数字时，最多可以有三个质数。

让我们来看一个例子来理解这个问题：

输入：N = 55

输出：53 + 2

解决方案：

奇数可以表示为质数之和。考虑到这些质数，我们有三种情况。

情况 1：如果 n 是质数，则它表示为一个质数 n 的和。
情况 2：如果 (n - 2) 是质数，则它表示为两个质数 n-2 和 2 的和。

情况 3：(n - 3) 是一个偶数，可以使用哥德巴赫猜想的方法表示为两个质数之和，在这种方法中，我们将检查一个数 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

sudhir sharma

更新于：2021年1月22日

321 次浏览

开启您的 职业生涯

完成课程获得认证

开始学习