欧拉函数
\(1\sim N\)中与\(N\)互质的数的个数被称为欧拉函数，记为\(\varphi(N)\)。
若在算术基本定理中，\(N=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}\)，则：

\[\varphi(N)=N*\prod_{质数p|N}(1-\frac{1}{p}) \]

证明：
容斥原理。
线性筛欧拉函数：

for (int i = 2; i <= n; i++) phi[i] = i;
	for (int i = 2; i <= n; i++) {
		if (phi[i] == i)
			for (int j = i; j <= n; j += i)
				phi[j] = phi[j] * (i - 1) / i;
	}