我已经頽到打模板的题解了
本题是埃氏筛模板题
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，
是一种由希腊数学家埃拉托斯特尼所提出
的一种简单检定素数的算法.
感谢度娘所提供的解释
埃氏筛简单来讲就是将一定范围内的数的除自身以外的所有倍数剔除,剩下的就是素数,在这里主要说一下这种方法的优化
Step 1
剔除除2以外的所有0<n<maxn的偶数
Step 2
剔除除1以外的所有0<n<maxn的奇数除自身以外的倍数
在此可加一个小小的优化
for(int i=3;i<=n;i++){
if(!f[i]){
for(int j=i*2;j<=n;j+=i){
f[j]=true;
}
}
}
这里的
if(!f[i]){
指此数未被判定为能被其他数整除的数(合数)
有什么好处?
当此数被判定为能被其他数整除的数(合数)时，此数的倍数必定也已经被判定为能被其他数整除的数(合数)，如果此时再次剔除此数的倍数便会重复操作时间复杂度便会增加
具体实现部分的代码如下
void work_prime(int n)
{
for(int i=4;i<=n;i+=2){
f[i]=true;
}
for(int i=3;i<=n;i++){
if(!f[i]){
for(int j=i*2;j<=n;j+=i){
f[j]=true;
}
}
}
}