C++ 中求和等于给定 N 的最大素数

在这个问题中，我们给定一个数字 n。我们的任务是找到素数的最大数量，其和等于给定的 N。

在这里，我们将找到当相加时等于该数字的最大素数数量。

素数是可以被自身或 1 整除的数字。

让我们举个例子来理解这个问题 -

输入 - N = 9

输出 - 4

解释 -

9 can be repressed as the sum of prime numbers in the following ways:
2, 2, 2, 3
3, 3, 3
2, 2, 5
2, 7
Out of these the maximum number of primes used is 4.

使用的素数的最大数量将基于可以相加得到该和的最小素数的数量。

因此，最小的素数是 2。而接下来更大的素数是 3，它是奇数。

因此，如果我们在计算总和时仅使用 2 和 3，则计数将达到最大值。基于此，我们可以将问题分为两种情况 -

情况 1 - 如果 N 是偶数，则总和中的所有素数都将是 2。因此，计数将为 n/2。

情况 2 - 如果 N 是奇数，则总和中的所有素数都将是 2，除了一个将是 3。因此，计数将为 (n-1/2)。

示例

C++ 中求和等于给定 N 的最大素数的程序

 实时演示

#include <iostream>
using namespace std;
int maxPrimeCount(int n){
   //For odd case the result will same as (n-1)/2
   return n / 2;
}
int main(){
   int n = 9;
   cout<<"The maximum number of primes whose sum is equal to "<<n<<" is "<<maxPrimeCount(n);
   return 0;
}

输出

The maximum number of primes whose sum is equal to 9 is 4

Narendra Kumar

更新于: 2020-06-03

123 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习