什么是欧拉函数？
欧拉函数记作 \(\varphi(n)\)，用来统计从 1 到 n 之间，有多少个正整数与 n 的最大公约数为 1——也就是与 n 互质的整数个数。举个例子，\(\varphi(9) = 6\)，因为 1、2、4、5、7、8 这六个数都与 9 互质。欧拉函数是数论中的基础概念，在密码学领域应用广泛，其中最著名的就是 RSA 算法：\(\varphi(n)\) 决定了生成密钥时所用的模逆元。
如何使用这个计算器
输入任意一个正整数 n，点击计算即可。工具会先把 n 分解成不同的质因数，再套用乘积公式，瞬间给出 \(\varphi(n)\) 的结果，并列出找到的所有不同质因数。无论是小数字还是高达十亿的大数字，都能轻松处理。
公式详解
计算欧拉函数最高效的方法是乘积公式：
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$
其中乘积取遍能整除 n 的每一个不同质数 \(p\)。
你只需要用到不同的质数，而不必关心它们各自出现的次数（幂次）。每一个因子 \(\left(1 - \frac{1}{p}\right)\) 都会剔除掉那些能被该质数整除的数所占的比例。
实例演算
以 \(n = 36\) 为例。它的质因数分解为 \(2^2 \times 3^2\)，所以不同的质数是 2 和 3。于是：
$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$
因此，1 到 36 之间恰好有 12 个整数与 36 互质。
常见问题
\(\varphi(1)\) 等于多少？ 按照惯例，\(\varphi(1) = 1\)，因为 1 与它自身互质。
质数 p 的 φ 值是多少？ 对任意质数 \(p\)，\(\varphi(p) = p - 1\)，因为从 1 到 \(p-1\) 的每个整数都与 p 互质。
欧拉函数是积性函数吗？ 是的。如果 \(\gcd(a, b) = 1\)，那么 \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\)。这正是为什么对不同质数取乘积的公式能够成立的原因。
