今天来玩玩筛
英文：Sieve
有什么筛？
这里介绍：素数筛，欧拉筛，约数个数筛，约数和筛
为什么要用筛？
顾名思义，筛就是要漏掉没用的，留下有用的。最终筛出来1~n的数的一些信息。
为什么要用线性筛？
考虑最基础的线性筛素数，是O(n)的。
而一般的做法是：
1.对于每个m暴力枚举1~sqrt(m)看能否被整除。O(nsqrt(n))
2.对于每个找到的素数，用它去将所有它的倍数的数都干掉。O(nlogn)
但是，即使是第二种，也有一个log
这是因为一个合数会被它的所有质因子筛一次。要重复质因子个数次，除第一次之外都没用。
所以用线性筛
线性筛原理：
一个算法，使得每个合数只被它的最小质因子筛一次。
怎么保证呢？
素数线性筛：
先看代码：
#include<bits/stdc++.h>
using namespace std;
const int N=10000000+10;
int ps[N],cnt;
bool v[N];
int n,m;
void sieve(){
for(int i=2;i<=n;i++){
if(v[i]==0){
ps[++cnt]=i;
}
for(int j=1;j<=cnt;j++){
if(i*ps[j]>n) break;
v[i*ps[j]]=1;
if(i%ps[j]==0) break;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
sieve();
v[1]=1;
int t;
for(int i=1;i<=m;i++){
scanf("%d",&t);
if(v[t]) printf("No\n");
else puts("Yes");
}
return 0;
}
看不懂...................
解释:
对于一个质数，之前没有被标记。肯定只会有一次查到。把它记录到素数集合里去。
然后，不论这个数是否为质数，都将已有的质数从1~cnt循环一遍，把所有的i*ps[j]标记。
当i*ps>n break，可以理解。
当i%ps==0 break.？？？
这个时候，ps和i不互质了，而ps第一次整除i，所以ps就是i的最小质因数。叫他ps0
而之后，ps更大，ps*i的最小质因数就不是ps了。因为i里有ps0，这个合数就等着以后i更大了，通过ps0筛掉。
ps再大，后面的ps*i的最小质因数都不是ps，所以之前直接break掉就好。
由于每个合数只会被i*ps的形式找到一次（那一次的ps就是这个合数的最小质因子）。而内层循环每一次都对应一个将v[ps*i]=1的操作。
所以内层循环均摊O(1)，总共O(n)
完毕。
欧拉线性筛：
代码：fai(i) 1~i中和i互质的数的个数。
可以容斥推出公式：假设：i=p1^q1*p2^q2*....pn^qn
那么，fai(i)=p1^(q1-1)*(p1-1) * p2^(q2-1)*(p2-1) * ......pn^(qn-1) * (pn-1)
证明不是本篇想讲的。
void sieve(){
fai[1]=1;
for(int i=2;i<=n;i++){
if(v[i]==0){
fai[i]=i-1;
pri[++cnt]=i;
}
for(int j=1;j<=cnt;j++){
if(i*pri[j]>n) break;
v[i*pri[j]]=1;
if(i%pri[j]==0) {
fai[i*pri[j]]=fai[i]*pri[j];break;
}
else{
fai[i*pri[j]]=fai[i]*(pri[j]-1);
}
}
}
}
并不想从积性函数性质入手解释。
显然的，当处理到fai[i]的时候，i的值应该就知道了。i是质数就现成赋值。
考虑公式。
当i%ps==0 时，i的质因子中有ps，那么i*ps的质因子ps的次数就大于一，那么，就是fai[i]*ps了
否则，i*ps 的 ps的次数就是1，那么，ps^(1-1)*(ps-1)=(ps-1) 所以是fai[i]*(ps-1)
之后的各种操作基于线性筛的要求和特质。（即每个数只被它的最小质因子筛一次）
例题：SDOI2008 仪仗队
约数个数线性筛：
推荐：线性筛约数个数和、约数和
设x=p1^q1*p2^q2*....pn^qn
要知道公式：个数=（q1+1）*(q2+1)*...*(qn+1) 乘法原理就可以知道。
设t[i]表示i的约数个数
设e[i]表示i的最小素因子个数
①i是质数：t[i]=2,e[i]=1;
②i%pj!=0 这个时候，pj里面没有i，根据积性函数，或者乘法原理，t[i*pj]=t[i]*t[pj]=2t[i]；
而 e[i*pj]=1
③i%pj==0 这个时候，pj里面至少有一个i，i也是pj的最小质因子。
t[i*pj]=t[i]/(e[i]+1)*(e[i]+2) 考虑公式，i*pj只在pj的位置上加了1，所以先除掉，再乘上去。
e[i*pj]=e[i]+1 最小素因子个数多了一个。
约数和的线性筛：
(很详细的解释）
设x=p1^q1*p2^q2*....pn^qn
首先还是要知道公式：和=(1+p1^1+...+p1^q1)*(1+p2^1+...+p2^q2)*...*(1+pn^1+...+pn^qn)
证明很简单，加数的个数显然就是约数个数，每次选择就是这个约数个数的质因数分解形式，数值就是这个约数的数值。
设t[i]表示i的约数和
设e[i]表示i的最小素因子对约数和的答案的贡献，即：(1+p1^1+...+p1^q1)（假设p1是最小质因子）
①当i是质数的时候，t[i]=i+1;e[i]=i+1;
②i%pj!=0 根据公式、积性函数性质 : t[i*pj]=t[i]*t[pj]
e[i*pj]=1+pj;
③i%pj==0
t[i*pj]=t[i]/e[i]*(pj*e[i]+1)
证明：考虑公式，i里面有pj的贡献，乘了一个pj，相当于多了一个pj^(qj+1)所以除掉后，乘上错位，再加一
而 e[i*pj]=e[i]*pj+1
就这样。代码参考上面的写就是了，没什么难度。
莫比乌斯函数筛：
知道定义就好说：
μ(i)={
0 i有平方因子
1 i的质因子个数为偶数
-1 i的质因子个数为奇数
}
根据定义直接筛就好了。
void sieve(){
u[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]){
u[i]=-1;
pr[++cnt]=i;
}
for(int j=1;j<=cnt;j++){
if(pr[j]*i>N) break;
vis[pr[j]*i]=1;
if(i%pr[j]==0) {
u[pr[j]*i]=0;break;
}
else u[pr[j]*i]=-u[i];
}
}
}
例题：bzoj2440 完全平方数