欧拉筛的应用：在线性时间（O(N)）内求出 1~N 的欧拉函数

之前学习了欧拉函数以及几个性质，知道了“欧拉函数 $\varphi(n)$ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目。”对于求解单个的 $\varphi(x)$ 很简单，直接枚举就可以了；但是如果要你在 $\Theta (N)$ 时间复杂度内求 $\varphi(i)$ 的值（$i=1,2,\dots,n$），怎么求呢？自然是用欧拉筛了～

几个性质

要用欧拉筛求解 1～N 的欧拉函数，需要用到几个性质：

0. 欧拉函数是积性函数，即 $\varphi(nm)=\varphi(n)\ast \varphi(m)$。上次证明过。（其实是证明性质 3 要用）

1. 当 $p$ 为质数时，$\varphi(p)=x-1$。这条上次已经证明过。

2. 对于质数 $p$，如果 $p|i$，那么 $\varphi(i\ast p) = p \ast \varphi(i)$。这个上次也证明过了。

3. 对于质数 $p$，如果不满足 $p|i$，那么 $\varphi(i\ast p) = (p-1) \ast \varphi(i)$。这个要证明下……

一些证明

对于第一条性质和第二条性质，之 前 都证明过了；

下面证明第三条性质：

因为 $p$ 是质数而不满足 $p|i$，所以 $p$ 与 $i$ 互质，即 $(p,i)=1$。 根据性质 0，满足：$\varphi(i \ast p)=\varphi(i)\ast \varphi(p)$。 又根据性质 1，满足：$\varphi(i \ast p)=\varphi(i)\ast (p-1)$。得证。

求 1～N 的欧拉函数

首先复习一下欧拉筛：

inline void BuildPrime(){
    vis[1]=false;
    for (int i=2;i<=N;i++){
        if (vis[i]) prime[++prime[0]]=i;
        for (int j=1;j<=prime[0];j++){
            if (i*prime[j]>N) break;
            vis[i*prime[j]]=false;
            if (i%prime[j]==0) break; // 如果再往后，prime[j] 就不是 i*prime[j] 的最小质因子了，所以不需要继续了
        }
    }
}

直接是枚举素数的。所以结合上面的性质，很容易得出求欧拉函数版的欧拉筛：

inline void BuildPhi(){
	phi[1]=1;
	memset(vis,1,sizeof(vis));
	vis[1]=false;
	for (int i=2;i<=N;i++){
		if (vis[i]){
			phi[i]=i-1;
			prime[++prime[0]]=i;
		}
		for (int j=1;j<=prime[0];j++){
			if (i*prime[j]>N) break;
			vis[i*prime[j]]=false;
			if (i%prime[j]) phi[i*prime[j]]=(prime[j]-1)*phi[i];
			else {phi[i*prime[j]]=prime[j]*phi[i];break;}
		}
	}
}