本文主要是介绍求n以内的的素数——埃氏筛法和欧拉筛法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求N以内的素数，朴素算法对于10^7之类的大数无疑是要超时的。时间复杂度为O（N^2）和O（N）
所以就需要一个效率更加高的方法来进行素数筛选。
1.Eratosthenes筛法（埃氏筛法）
时间复杂度：O(n*lglgn)（ 约等于 O（n*1.5） ）
筛法的思想：对于不超过N的每个非负整数p，删除2p,3p,4p,...,但处理完所有数之后，还没有被删除的就是素数。可用标志数组bk[i]来判断i是否被删除了。代码如下：
bool bk[1000];
memset(bk,1,sizeof(bk));
for(int i = 2; i <= N; i++)for(int j = i*2; j <= N;j += i ){bk[j] = 0;}
下面来模拟一下这个过程：
假设N = 20；
这份代码已经相当高效了。给定外层的循环变量i，内层的循环次数是 floor&#x
这篇关于求n以内的的素数——埃氏筛法和欧拉筛法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
