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

C++实现素数筛法

2023-06-26 18:21:42 深夜i -- --

C++ 素数筛法算法循环

素数是指只能被1和它本身整除的正整数，如2、3、5、7、11等。在计算机科学中，素数被广泛应用于密码学、哈希表、质因数分解等领域。在搜索一定范围内的素数时，可以使用素数筛法，它可以在O(n)的时间复杂度内找到所有小于等于n的素数。下面我们来介绍一下如何使用C++实现素数筛法。

首先，我们定义一个数组prime[]，用于标记素数，初值全部为1，即全部视为素数。然后，将2到n间的所有素数找出来，将其倍数标记为0，以此筛掉所有合数。最后，所有标记为1的下标即为素数。

下面是C++代码实现：


#include<iostream>
using namespace std;
const int MAXN = 1000000;
int prime[MAXN + 5]; //筛法中的标记数组
int main()
{
  int n;
  cin >> n;
  //初始化数组
  for (int i = 2; i <= n; i++) 
    prime[i] = 1;
  
  //筛掉所有合数
  for (int i = 2; i <= n; i++)
  {
    if (prime[i])
    {
      for (int j = 2 * i; j <= n; j += i)
        prime[j] = 0;
    }
  }
  
  //输出所有素数
  for (int i = 2; i <= n; i++)
  {
    if (prime[i])
      cout << i << " ";
  }
  
  return 0;
}

以上代码中，首先定义了一个数组prime[]，并将其全部初始化为1表示素数。接着，从2开始遍历数组，如果当前下标i指向的数字为素数，则从其2倍开始，依次将其倍数标记为0，即表示合数。最后遍历prime[]数组，输出其下标为素数的值即可。

使用素数筛法，可以方便地找到小于等于n的素数，且时间复杂度较低。在实际应用中，可以使用该算法进行密码学中的公钥加密、哈希函数中的质数选取、质因数分解等计算。

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

下一篇: 什么是修复C++？

评论区

()

相似文章