朴素筛法
#include<cstdio>
using namespace std;
const int sz=1e6+1;
int n,i,j,a[sz],b[sz],ct;
int main()
{
scanf("%d",&n);
for(i=2;i<=n;++i)
if(!a[i])
{
b[++ct]=i;
for(j=i<<1;j<=n;j+=i)a[j]=1;
}
printf("%d",ct);
return 0;
}
线筛
#include<cstdio>
using namespace std;
const int sz=1e6+1;
int n,i,j,a[sz],b[sz],m;
int main()
{
scanf("%d",&n);
for(i=2;i<=n;++i)
{
if(!b[i])b[i]=a[++m]=i;
for(j=1;j<=m&&a[j]*i<=n;++j)
b[i*a[j]]=i;
}
printf("%d",m);
return 0;
}
比较
比较下来显然是线筛更优。
朴素的办法大家更容易想到也更好理解而线筛则把重复的情况缩减了很多很多。
因为线性筛法是从大到小累计质因子这样来标记每一个合数,在i之上我们尽量只累计一个质数。
也就是这个数的最小质因子所以很不容易会有重合。
上面的模板是蓝书上面的模板变形。(因为是自己平常打的所以有点不一样)
orz
if(i%b[j]==0)break;
而Y总的模板我感觉效率会更高。
这个break跳过了很多无用功。