21xrx.com
2025-06-18 17:26:19 Wednesday
文章检索 我的文章 写文章
C++实现质数筛选代码
2023-07-02 15:20:40 深夜i     23     0
C++ 质数 筛选 代码 实现

质数筛选是算法中的一个经典问题，而 C++ 是一门广泛使用的编程语言。在这篇文章中，我们将讨论如何使用 C++ 实现质数筛选代码。

质数筛选是一种算法，用于找到一定范围内的所有质数。它的基本思路是从 2 开始遍历每一个数，并将它们的倍数标记为合数。最终，没有被标记的数字就是质数。

下面是使用 C++ 实现质数筛选的代码：

#include<iostream>
using namespace std;
const int MAXN = 1e6 + 5; // 素数表的最大范围
int prime[MAXN], is_prime[MAXN]; // 存放质数和标记数组
int sieve(int n){ // 筛选质数的函数
  int p = 0;
  for(int i=2;i<=n;i++){ // 从2开始遍历每个数
    if(!is_prime[i]) prime[p++] = i; // 如果是质数，存入 prime 数组
    for(int j=0;j<p && i*prime[j]<=n;j++){ // 将 i 的倍数标记为合数
      is_prime[i*prime[j]] = 1;
      if(i%prime[j] == 0) break; // 已经标记过的数不需要再次标记
    }
  }
  return p; // 返回质数的个数
}
int main(){
  int n = 100; // 筛选范围
  int cnt = sieve(n); // 调用 sieve 函数
  for(int i=0;i<cnt;i++) cout<<prime[i]<<" "; // 输出筛选出的质数
  return 0;
}

在上面的代码中，我们首先定义了两个数组 prime 和 is_prime，用于存放质数和标记数组。然后，我们定义了一个函数 sieve，用于筛选质数。该函数接受一个正整数 n，表示筛选的范围。在函数中，我们从 2 开始遍历每一个数，并将它们的倍数标记为合数。最终，没有被标记的数字就是质数，并将它们存入 prime 数组。

在主函数中，我们定义了一个 n 变量，表示筛选的范围。然后，我们调用 sieve 函数，并将质数的个数存入 cnt 变量。最后，我们遍历 prime 数组，并输出所有的质数。

这就是使用 C++ 实现质数筛选代码的全部内容。如果你正好在学习 C++，并且想要练习算法问题，可以尝试编写这个问题的解法，加深自己的理解。

  
  

评论区