筛选法求素数

筛选法求素数要比普通的求素数方法更加快速，虽然在一些小范围内看不出多大差别，但是当范围大到一定程度，普通求素数的方法就会显得比较耗时，在做一些编程题的时候特别容易超时
我们就拿1000以内的素数来说

普通的方法（可能和我的不一样，但是都是按照定义来的，意思差不多） #include<iostream> using namespace std; int main() {int a[200];int i,j,cnt=0;for(i=2;i<1000;i++){for(j=2;j<=i;j++){if(i%j==0)break;}if(i==j)a[cnt++]=i;这样就可以把1000以内的素数全部存到数组a中elsecontinue;}for(int i=0;i<=cnt;i++)cout<<a[i]<<endl; }

可以看到1000以内的每一个数都要进行一次第二个for循，而且第二个for循环每一次都要循环完，这样就耗时

接下来用筛选法求素数来试试 #include<iostream> using namespace std; int main() {int a[1000]={0};//这里最好初始化一下，因为有时候取数组大了数组里边的初始值不是0而是一些后台的垃圾数据int b[1000]={0};int cnt=0;for(int i=2;i<1000;i++){if(a[i]==0){b[cnt++]=i;for(int j=2;i*j<1000;j++)a[j*i]=1;//所有是素数的倍数的数都可以去除}}for(int i=0;i<cnt;i++)cout<<b[i]<<endl;}

可以看出来代码明显要短，可能代码比普通代码要难理解一点
至于为啥它不用再从2~n每一个都除一遍，因为每一个不是素数的数都是由一些比自己小的两个整数相乘得到
筛选法求素数又是从2（本身是素数）开始，之后的像4，6，8，都会因为是2的倍数而使a[4],a[6],a[8]的值从0变成1；
不用进行判断，以此类推那些比自己小的数只要不是素数都已经使数组对应值变成1，由此把所有素数找出来，比普通的要简单多

总结

以上是生活随笔为你收集整理的筛选法求素数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。