C++求小于等于n的素数之和 |21xrx.com

C++求小于等于n的素数之和

2023-07-09 21:07:16 深夜i -- --

C++ 素数求和 n

要求小于等于n的素数之和，需要首先了解什么是素数。素数是指只能被1和它本身整除的正整数，如2、3、5、7等。

接下来，我们可以通过筛法来求解小于等于n的素数之和。筛法的基本思想是从2开始，将其所有倍数标记为合数，然后再从下一个未标记的数开始重复这个过程，直到我们筛选完所有小于等于n的数。最后，将所有未被标记为合数的数相加，即可得到小于等于n的素数之和。

下面是C++的代码实现：


#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000000;
bool prime[MAXN+1];   //用于判断是否为合数
int sum[MAXN+1];     //存储小于等于n的素数之和
void getPrime(int n){
  memset(prime,true,sizeof(prime)); //初始化为true
  for(int i=2; i<=n; i++){
    if(prime[i]){
      for(int j=i*2; j<=n; j+=i){ //将i的倍数标记为合数
        prime[j] = false; 
      }
    }
  }
  sum[0] = 0;
  for(int i=1; i<=n; i++){
    sum[i] = sum[i-1] + (prime[i] ? i : 0);  //计算小于等于i的素数之和
  }
}
int main(){
  int n;
  cin >> n;
  getPrime(n);
  cout << sum[n] << endl;
  return 0;
}

在代码中，我们使用的是bool类型的prime数组来判断是否为合数，如果是则为false。然后，我们通过一个循环遍历从2到n之间的每个数，将它的倍数标记为合数。最后，根据存储素数之和的数组sum，我们可以得到小于等于n的素数之和。

使用上述代码，我们就可以很方便地求出小于等于n的素数之和。

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

下一篇: C++实现非阻塞监听按键操作

评论区

()

相似文章