21xrx.com
2024-11-05 14:39:19 Tuesday
登录
文章检索 我的文章 写文章
C++实现筛法求素数
2023-06-30 02:40:30 深夜i     --     --
C++ 筛法 素数

素数是指只能被1和本身整除的正整数,例如2、3、5、7等。求解素数是计算机算法中的常见问题之一。在本文中,我们将介绍C++实现筛法求素数。

筛法又称埃氏筛法,是一种简单有效的算法,可以在一个数列中快速筛出素数。这个算法的操作流程如下:

1. 先将2~n的各数放入表中;

2. 取出2,然后将2的倍数从表中删除;

3. 取出下一个素数3,重复步骤2,直到所有小于或等于n的质数全部找出。

以下是C++实现筛法求素数的核心代码:


void sieve_of_eratosthenes(int n)

{

  bool* prime = new bool[n+1];

  //初始化数组为true,表示都是素数

  for(int i=2; i<=n; i++)

  {

    prime[i] = true;

  }

  //筛选素数

  for(int i=2; i*i<=n; i++)

  {

    if(prime[i])

    {

      for(int j=i*i; j<=n; j += i)

      {

        prime[j] = false;

      }

    }

  }

  //输出素数

  for(int i=2; i<=n; i++)

  {

    if(prime[i])

    

      cout << i << " ";

    

  }

  delete[] prime;

}

此函数采用了动态内存分配,先将所有数初始化为素数,然后从2开始,每一次循环都找到当前未标记为非素数的最小数(即素数),然后把它的倍数全部标记为非素数。最后输出所有标记为素数的数。

以上是C++实现筛法求素数的方法,可以在较短的时间内得到小于等于某个数的全部素数。

  
  

评论区

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