C++ 素数求和 |21xrx.com

C++ 素数求和

2023-07-04 03:20:59 深夜i -- --

C++ 素数求和

素数是指只能被1和它本身整除的正整数。在编程领域中，素数的求和是一个经典而有趣的问题，也是对编程能力的考验之一。在数字计算的学科中，C++语言常常被用来解决这个问题。

首先，我们需要明白一些计算素数的基本方法和原理。要判断一个数是不是素数，最朴素的方法当然是逐一判断每个小于它的正整数是否是它的因子。但这样显然效率低下，而且随着数的增大，计算时间也会随之指数级增长，完全不可行。

因此，我们需要寻找更加高效的算法。一个比较经典的算法就是所谓的“筛法”。具体来说，我们可以把所有小于等于n的素数打出一个表，从小到大枚举这个表中素数的倍数，然后把这些数都标记为合数（即不是素数）。这样，当我们枚举到后面的素数时，就可以排除掉这些被标记的数，从而避免了不必要的计算。这个过程一直进行到我们找到第k个素数为止，其中k是一个预先给定的正整数。

在C++中，我们可以采用如下代码实现求素数和的算法：


#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000000;
bool prime[MAXN + 1];
int sum[MAXN + 1];
int main()
{
  memset(prime, true, sizeof(prime));
  prime[0] = prime[1] = false;
  for (int i = 2; i <= MAXN; i++)
  {
    if (prime[i])
    {
      for (int j = i + i; j <= MAXN; j += i)
      {
        prime[j] = false;
      }
    }
  }
  sum[0] = 0;
  for (int i = 1; i <= MAXN; i++)
  {
    sum[i] = sum[i - 1] + (prime[i] ? i : 0);
  }
  int n;
  while (cin >> n)
  {
    cout << sum[n] << endl;
  }
  return 0;
}

上述代码首先采用布尔型数组prime来记录每个数是否是素数，其中初始化时全部标记为true，然后排除掉0和1两个非素数。接着，我们从2开始枚举每个数i，如果它是素数，就把它的所有倍数都标记为合数。这里是通过“每次加上自己的值”的方法实现的。

由于每个素数都是它本身，所以如果某个数i是素数，那么相当于把i的所有倍数都标记为了合数，后面再枚举这些数就可以省略掉了。最后，我们再使用累加和的方式计算出所有小于等于MAXN的素数的和，存储到sum数组中。

进一步地，我们可以通过输入一个正整数n，输出1到n之间所有素数的和来验证我们算法的正确性。C++作为高效的编程语言，它在求解问题的速度和效率方面有着得天独厚的优势，这也为大量计算项目的实现提供了可靠的支持。

上一篇: idea打包java可执行jar包

下一篇: C++中的\r是什么意思？

评论区

()

相似文章