Bases
这里给出的筛法是以线性筛素数的方法为基础的。
利用了欧拉函数是积性函数的性质:对于任意互质的数(a),(b),有(f(a*b)=f(a)*f(b))
筛法
类比于线性筛素数。
(i)以下的欧拉函数已经被筛出，我们利用(i)和(prim)往后更新。
如果(i)是素数，那么(varphi(i)=i-1)
如果(i\%prim[j]!=0) ,那么((i,prim[j])==1), 则有(varphi(i*prim[j])=varphi(i)*varphi(prim[j])=varphi(i)*(prim[j]-1))
如果(i\%prim[j]==0)，则(varphi(i*prim[j])=varphi(i)*prim[j])（先甩结论）
有两个证法：
1.
(i\%prim[j]==0)不能直接算的原因是它两个不互质，那我们把它写成互质的样子。
设(i*prim[j]=A*prim[j]^{m-1}*prim[j]=A*prim[j]^m)
有个结论：如果(p)是质数，那么(varphi(p^k)=p^k-p^{k-1}=p^{k-1}*(p-1))
比较显然，(p^k)是数的总数，而(p^k)只有(p)这一个质因子，所以它的因数都是(p)的倍数，即(1*p,2*p,3*p,...,p^{k-1}*p)，(p^k)的包含自己在内的因数个数有(p^{k-1})个。
用总数(p^k)减去因数个数(p^{k-1})就是 (varphi (p^k))。（这里总数和因数个数都算了自己本身，一减就把自己减掉了，所以没有影响）
(varphi(p^k)=p^{k-1}*(p-1))
(varphi(p^{k-1})=p^{k-2}*(p-1))
联立以上二式可得：(varphi(p^k)=varphi(p^{k-1})*p)
以下将(prim[j])简写成(p)
(varphi(i*p)=varphi(A)*varphi(p^{m})=varphi(A)*varphi(p^{m-1})*p)
而(A*p^{m-1}=i),则(varphi(A)*varphi(p^{m-1})=varphi(i))
那么(varphi(i*p)=varphi(A)*varphi(p^{m-1})*p=varphi(i)*p)
(Q.E.D.)
2.
欧拉函数有个通式：（先甩式子再证明）
(varphi(n)=n*(1-frac{1}{p_1})*(1-frac{1}{p_2})*...*(1-frac{1}{p_n}))，(p_i)是质因数
那么
(varphi(i)=i*(1-frac{1}{p_1})*(1-frac{1}{p_2})*...*(1-frac{1}{prim[j]}))
(varphi(i*prim[j])\=(i*prim[j])*(1-frac{1}{p_1})*(1-frac{1}{p_2})*...*(1-frac{1}{prim[j]})\=i*(1-frac{1}{p_1})*(1-frac{1}{p_2})*...*(1-frac{1}{prim[j]})*prim[j]\=varphi(i)*prim[j])
然后来说一下那个什么通式怎么来的：
这里也给出两个证法：
1.容斥原理
设(n)的其中一个质因子是(p) ，([1,n])中(p)的倍数有(p,2p,3p,...frac n p*p)一共(frac n p)个数，([1,n])中不含因子(p)的数就一共有(n-frac n p)个
设(n)的另外一个质因子是(q)，同理可得([1,n])中不含因子(q)的数就一共有(n-frac n q)个，根据容斥原理，([1,n])中两个质因子均不含的数的个数为(n-frac n p-frac n q+frac n {pq}=frac {n(pq-q-p+1)} {pq}=frac{n(p-1)(q-1)}{pq}=n*frac{p-1}p*frac{q-1}q=n*(1-frac 1 p)*(1-frac 1 q))
推广到(n)的每一个质因子(变形时用到了分组分解因式的方法)，可得([1,n])中所有(n)的质因子均不含的数的个数为(n*prod_{i=1}^k(1-frac 1 {p_i}))，其中，(p_i)是(n)的质因子。
即(varphi(n)=n*prod_{i=1}^k(1-frac 1 {p_i}))
2.利用积性函数的性质
(n=0)时，(varphi(n)=0) 成立
(n=1)时，(varphi(n)=1) 成立
(n)为质数时,(varphi(n)=n-1) 成立
(n)为一个质数的正整数次幂，即(n=p^k)时，(varphi(p^k)=p^k-p^{k-1}=p^{k}*(1-frac1 p)=n*(1-frac1 p)) 成立
(n)为任意正整数时，根据算术基本定理可得(n=p_1^{k_1}p_2^{k_2}p_3^{k_3}...p_m^{k_m})，其中(p_i)为质因数
根据积性函数的性质(varphi(n)\=varphi(p_1)varphi(p_2)...varphi(p_m)\=p_1^{k_1}(1-frac 1{p_1})p_2^{k_2}(1-frac 1{p_2})p_3^{k_3}(1-frac 1{p_3})...p_m^{k_m}(1-frac 1{p_m})\=n*(1-frac 1{p_1})(1-frac 1{p_2})...(1-frac 1{p_m}))
$Q.E.D . $
（怎么觉得证明通式比证明这个结论本身还要复杂
Code View
void Phi()
{
for(int i=2;i<=n;i++)
{
if(!vis[i]) prim[++pn]=i,phi[i]=i-1;
for(int j=1;j<=pn&&i*prim[j]<=n;j++)
{
vis[i*prim[j]]=1;
if(i%prim[j]==0)
{
phi[i*prim[j]]=phi[i]*prim[j];
break;
}
else phi[i*prim[j]]=phi[i]*(prim[j]-1);
}
}
}