埃氏筛
用每个小于等于 \sqrt{n} 质数去把所有它小于等于 n 的倍数都判为不是素数。
欧拉筛
欧拉筛优化了埃氏筛，做到了每个数都被它最小的因子筛去。
for(int i=2;i<=n;++i)
{
if(vis[i]==0) p[++cnt]=i;
for(int j=1;j<=cnt&&i*p[j]<=n;++j)
{
vis[i*p[j]]=1;
if(i%p[j]==0) break;//欧拉筛的关键，如果这个数不是最小质因子，就结束
}
}
练习
筛法都只能筛素数吗，不。
欧拉函数
欧拉函数： \varphi(i) 表示所有 ≤i 的和 i 互质的个数。
积性函数
满足 f(p)f(q)=f(pq) 其中 p,q 是质数的叫积性函数。
满足 f(p)f(q)=f(pq) 的叫完全积性函数。
筛积性函数
暴力
暴力枚举，不用说。
欧拉筛
对于一个质数我们可以直接求出它的值。
因为是积性函数所以可以在筛的过程中把它拆成 i*p_i 再乘一下就行。
练习
杜教筛
不要以为我不会，其实我就是不会