C++实现筛选法求素数 |21xrx.com

C++实现筛选法求素数

2023-07-01 00:26:09 深夜i -- --

C++ 筛选法素数

素数，也叫质数，是指在大于1的自然数中，除了1和该数本身之外，没有其他因子的数。素数是数学中的基础概念，在加密算法、数论和数据结构等领域都有广泛的应用。

C++是一种高级编程语言，它是为系统和应用程序设计的一种通用编程语言。在C++中，我们可以用筛选法来求素数。筛选法是一种较为高效的求素数方法，它可以在较短的时间内找出一定范围内的所有素数。

筛选法的基本思想是，首先将所有自然数标记为“未筛选”，然后从2开始不断筛选，对于每个素数p，将他的倍数标记为“已筛选”，这样，剩余的未筛选的数就是素数。具体实现时，可以用一个布尔型数组来标记每个自然数是否被筛选过。

下面是一个用C++实现筛选法求素数的示例程序：


#include <iostream>
#include <cmath>
using namespace std;
void sieve(int n)
{
  bool prime[n+1]; //定义一个bool类型的数组，用于标记每个数是否为素数
  memset(prime, true, sizeof(prime)); //将数组所有元素初始化为true，表示都是素数
  for (int p=2; p*p<=n; p++)
  {
    if (prime[p] == true)
    {
      //将p的所有倍数标记为合数
      for (int i=p*p; i<=n; i+=p)
        prime[i] = false;
    }
  }
  //输出所有素数
  for (int p=2; p<=n; p++)
    if (prime[p])
     cout << p << " ";
}
int main()
{
  int n;
  cout << "请输入一个正整数n：";
  cin >> n;
  cout << "1-" << n << "范围内的素数有：";
  sieve(n);
  cout << endl;
  return 0;
}

在该程序中，我们先定义了一个bool类型的数组prime，用于标记每个数是否为素数。然后，我们将数组中所有元素初始化为true，表示它们都是素数。接着，我们从p=2开始枚举每个素数，对于每个素数p，我们将它的所有倍数标记为“已筛选”，这样每个未筛选的数都是素数。

最后，我们输出所有素数，即数组中值为true的下标所对应的数。在程序中，我们要求用户输入一个正整数n，并输出1-n范围内的素数。

总的来说，C++实现筛选法求素数比较简单，但是需要注意程序中数组索引的边界问题。筛选法是一种高效的求素数方法，它在复杂度上比暴力枚举的方法要更加优秀。在实际编程中，我们可以运用筛选法，大幅提升程序的效率。

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

下一篇: C++输入数据时用空格隔开

评论区

()

相似文章