21xrx.com
2025-03-27 06:59:33 Thursday
文章检索 我的文章 写文章
C++实现素数筛算法
2023-06-27 00:46:28 深夜i     13     0
C++ 素数筛算法 实现

素数筛算法，可以高效地筛选出一定范围内的所有素数。C++是一种强大的编程语言，在实现素数筛算法时也有许多优秀的解决方案。

首先，我们需要明确素数的定义：一个数如果只能被1和自己整除，则它是素数。从2开始，一个一个判断是否为素数，会非常耗时。所以，我们采用一种高效的算法：埃氏筛法。

埃氏筛法，是以法国数学家埃拉托斯特尼斯（Eratosthenes, 约公元前276年–194年）命名的一种筛选素数的算法。其主要思路是从2开始，将2的倍数标记为合数，然后再取3，将3的倍数标记为合数，以此类推，直到所求范围内所有的数都被检查过。

现在，我们可以开始用C++实现。

首先，创建一个bool类型的数组，以记录每个数是否为素数。假设我们要筛选出100以内的素数，则创建一个101个数的数组，第0个数作为编号不使用，其余的都标记为素数。

bool isPrime[101];
for (int i = 2; i <= 100; i++) {
  isPrime[i] = true;
}

然后，从2开始，将2的倍数标记为合数，所以需要从2开始遍历数组。当我们遍历到一个素数，即当前的i为素数时，要将i的倍数都标记为合数。例如，当i为2时，将4、6、8……都标记为合数；当i为3时，将6、9、12……都标记为合数，以此类推。标记为合数的方式是将对应位置的isPrime数组的值设置为false。

for (int i = 2; i <= 100; i++) {
  if (isPrime[i]) {
    for (int j = 2 * i; j <= 100; j += i) {
      isPrime[j] = false;
    }
  }
}

最后，遍历数组，输出所有值为true的元素，即为筛选出的素数。

for (int i = 2; i <= 100; i++) {
  if (isPrime[i])
    cout << i << " "; // 输出素数
  
}

此时，完整的C++代码如下：

#include <iostream>
using namespace std;
int main() {
  // 创建素数判断数组
  bool isPrime[101];
  for (int i = 2; i <= 100; i++) {
    isPrime[i] = true;
  }
  // 筛选素数
  for (int i = 2; i <= 100; i++) {
    if (isPrime[i]) {
      for (int j = 2 * i; j <= 100; j += i) {
        isPrime[j] = false;
      }
    }
  }
  // 输出素数
  for (int i = 2; i <= 100; i++) {
    if (isPrime[i])
      cout << i << " ";
    
  }
  return 0;
}

这样，就可以高效地筛选出100以内的所有素数。在实际应用中，可以根据需要自行修改代码，实现更加灵活的素数筛选功能。

  
  

评论区

请求出错了