21xrx.com
2024-11-05 19:06:01 Tuesday
登录
文章检索 我的文章 写文章
C++实现素数筛算法
2023-06-27 00:46:28 深夜i     --     --
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以内的所有素数。在实际应用中,可以根据需要自行修改代码,实现更加灵活的素数筛选功能。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复