欧拉函数

欧拉函数

欧拉函数是小于或等于n的正整数中与n互质的数目，$\phi(1) = 1$。

通式：
$$
\phi(x)= x \mathop{\Pi}\limits_{i = 1}^{n}(1 - \frac{1}{p_i})
$$
若n是质数的p的k次幂，$\phi(n) = p^k - p^{k - 1}$，因为除了p的倍数$p * (1,2\dots p^{k - 1})$以外，其他数均与n互质。

线性筛，每个合数通过其最小的质因数筛掉。