本文主要是介绍埃式筛法+欧拉筛法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
浅谈筛法
- 试除法
- 埃式筛法
- 输出 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
- 欧拉筛法
埃式筛法与欧拉筛法的目的是一样的，都是将一段区间内合数删除，最后留下质数，不一样的是思想不同，效率不同，埃式是O(nloglogn)级别的，我也不懂，看网上的，欧拉筛法是线性的O(n)的，下面是找素数的几种方法
试除法
对于量级很小的几个数，直接对该数判断是不是素数就行了，代码如下：
bool check(int a,int b)
{for(int i=a;i<b;i++){for(int j=2;j<i;j++){if(i%j==0) return false; }}return true;}
埃式筛法
先见代码吧
bool num[50050];
int prime[50050];
void check(int x)
{for(int i=2;i*i<=x;i++){if(num[i]){for(int j=i*i;j<=x;j+=i){ // 或写成for(int j=i+i;j<=x;j+=i),两种方法都可，不过第一种更省事 num[j]=false;}}}
// 先用小于等于sqrt(x)的数对num【】数组操作完之后，以num【】数组为判别依据，把素数全放到素数数组； int k=0;for(int i=2;i<=x;i++){if(num[i]) prime[k++]=i;}
}
如果是i=2 num【4，6，8，10,12,14,16.。。】=false
i=3 num[9,12,15,18...]=false
i=5 num[25,30,35...]=false
是把sqrt(x)里的素数全筛出来，以该素数与各项【eg：i=2就有4，6，8，10，12，14 i=3就有9，12，15，18】往后迭代的积为合数，依次筛掉合数，以num【i】的真假为判别标准
int main()
{memset(num,true,sizeof(num));int n;cin>>n; check(n);for(int i=0;i<k;i++){cout<<prime[i]<<" ";}
}
输出
100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Process exited after 2.439 seconds with return value 0
欧拉筛法
写的注释比较多，这里就不废话了
bool num[50050];
int prime[50050];
int a,b;
int countnum=1;
//素数打表用欧拉筛法 不全以num【i】的真假为依据判别素数还是合数 ，重点在打表操作
void check()
{for(int i=2;i<=sqrt(b);i++){if(num[i])prime[countnum++]=i;for(int j=1;j<countnum;j++){ if(i*prime[j]>sqrt(b)) break;num[i*prime[j]]=false; if(i%prime[j]==0) break;}}
}
// 先依次将小于等于sqrt(x)的素数放到素数数组(因为后面的打表操作只需要这些数)，大于它的素数先不放(注意：这一点与埃式筛法不同)
void ansprint(int x)
{cout<<x<<"=";
// 进去的时候既有素数也有合数，合数的话eg：10=2*5 ， 12=2*2*3；这样打表做除法 for(int i=1;i<countnum;){if(x==1) break;else if(x%prime[i]==0){x/=prime[i];cout<<prime[i];if(x!=1) cout<<"*";}else if(i==countnum-1 && x!=1){cout<<x;x=1; } else i++;}cout<<endl;
}
int main()
{memset(num,true,sizeof(num));cin>>a>>b;check(); //离线打表 for(int i=a;i<=b;i++){ansprint(i);}
}
输出
2 10
2=2
3=3
4=2*“2
5=5
6=2*”3
7=7
8=2*“2*“2
9=3*”3
10=2*5
Process exited after 2.654 seconds with return value 0
学会的话可以做题练练手，下面是链接
链接: 点这里牛客寒假集训2021.
这篇关于埃式筛法+欧拉筛法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
