C++实现100以内素数筛选法 |21xrx.com

C++实现100以内素数筛选法

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

C++ 素数筛选法 100 实现

素数是自然数中非常重要的一个部分，为了方便处理，我们常常需要筛选出一定范围内的素数，C++可以通过筛选法实现这一操作。

首先，我们需要明确一下什么是素数。素数是除了1和自己之外没有其他因子的自然数，比如2、3、5、7等都是素数。相对的，能够分解为两个以上因子的自然数就不是素数。

接下来，我们介绍C++实现100以内素数筛选法的方法。在这个筛选法中，我们需要先初始化一张表格，并标出所有的数为质数，然后从2开始，将其所有的倍数标记为合数（即不是质数）。最终，未被标记的数即为素数。

以下是100以内素数筛选法的C++代码实现：


#include<iostream>
#include<cstring>
using namespace std;
const int N = 101;
bool is_prime[N];
int main(){
  memset(is_prime, true, sizeof(is_prime)); // 初始化is_prime数组为true
  for(int i = 2; i * i <= N; i++){ // 从2开始，遍历到sqrt(N)，将其倍数均设为不是素数
    if(is_prime[i]){
      for(int j = i * i; j <= N; j += i){
        is_prime[j] = false;
      }
    }
  }
  cout << "100以内的素数为：";
  for(int i = 2; i < N; i++){ // 遍历is_prime数组，输出素数
    if(is_prime[i])
      cout << i << " ";
  }
  cout << endl;
  return 0;
}

其中，bool类型的is_prime数组表示该索引对应的数是否为质数。首先，我们使用memset将数组初始化为true。然后，我们从2开始，遍历到sqrt(N)（即10），将起所有倍数均设为false。最后，我们遍历一遍is_prime数组，输出true对应的索引，即素数。

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

下一篇: Node.js 的 URL 模块

评论区

()

相似文章