锐客网

  1. 首页 > it技术 > >

质数判断与埃氏筛

质数判断 我们来看这么一道问题：

给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）N<=10000000，M<=100000
首先很容易联想到使用枚举法来确定题目的整体框架
for( i: 1~m) { cin>>x; if(x是质数) { yes; }else { no; } }

关键在于质数判断部分。
【质数判断与埃氏筛】质数的判断问题我们可以从定义出发。质数，又称素数，是除了1和它自身以外没有其他的因子。
bool isPrime(int x) { if(x==1) return false; for(int i=2; i

稍微计算下整体的时间复杂度，可以发现用时会比较多，那么我们可以思考下优化的地方。整体框架确定后，能优化的地方可从质数判断入手。思考，一个数去除以比它的一半还要大的数，一定是除不尽的，因此，除到x/2就够了。
再改进一下，一个数若可以进行因数分解，那么分解得到的两个数一个范围小于sqrt(x),另一个一定大于sqrt(x)。故，上述代码我们也只需要遍历到sqrt(x)就可以了。若在2~sqrt(x)找不到约数，那么一定不存在。
bool isPrime(int x) { if(x==1) return false; for(int i=2; i*i<=x; i++) { if(x%i==0) return false; } return true; }

再进一步进行优化，偶数一定不是质数
bool isPrime(int x) { if(x<2) return false; if(n%2==0) return false; for(int i=3; i*i<=x; i+=2) { if(x%i==0) return false; } return true; }

但当m,n很大的时侯这种方式的数量级依旧相当大。在一般的机子它不是一秒钟跑不出结果，它是好几分钟都跑不出结果。有没有更有效率的方法呢？
我们可以考虑使用筛法来进行处理。
埃氏筛 根据数学原理：一个合数总是可以分解成若干个质数的乘积，换个角度去理解，也就是说合数是某个质数的倍数。此时如果把质数的倍数都去掉，那么剩下的就是质数了。
这样的筛选方式叫做埃氏筛，也叫埃拉托色尼选筛法，是数学家埃拉托色尼提出的。
代码思路：
  1. 从质数2开始进行枚举
  2. 如果数字是质数，将范围内所有该数的倍数标记成非质数
  3. 继续向后枚举，直到遍历完范围内所有的数位置
代码实现：
#include #include using namespace std; bool isPrime[10000005]={0}; //标记数组 用来表示数字是否是质数 true-是质数 false-不是质数void aiPrime(int n) {// 埃氏筛处理n内的质数 memset(isPrime,true,sizeof(isPrime)); //所有数字，默认标记为质数 isPrime[1]=false; //修改1的状态，1不是质数for(int i=2; i<=n; i++)//从2开始，枚举范围n内的每个数字 { if(isPrime[i])//如果i是质数 {//将n范围内所有i的倍数，标记为非质数 for(int j=2; j*i<=n; j++) {//打底从两倍开始,j*i就是i的倍数 isPrime[i*j]=false; // 标记倍数为非质数 }} } }int main(int argc, char** argv) { int n,m,x; cin>>n>>m; aiPrime(n); for(int i=1; i<=m; i++) { cin>>x; if(isPrime[x]) { cout<<"yes\n"; }else { cout<<"no\n"; } }return 0; }

    推荐阅读


    上一篇：第三篇《淡》

    下一篇：你说想结婚，为什么女朋友没反应（）