欧拉函数笔记

定义 欧拉函数 $\varphi(n)$ 表示小于等于 $n$，且与 $n$ 互质的正整数的个数。 如何求 $\varphi(n)$？ 比如 $varphi(12)$ 把 $12$ 质因数分解，$12=2^2*3$，其实就是得到了 $2$ 和 $3$ 两个互异的质因子。 然后把 $2$ 的倍数和 $3$ 的倍数都删掉。 $2$ 的倍数：$2,4,6,8,10,12$ $3$...