欧拉函数：定义、公式、Python 实现及复杂度分析

欧拉函数定义 欧拉函数 $\varphi(n)$ 表示小于等于 $n$ 且与 $n$ 互质的正整数的个数。 欧拉函数计算公式 若 $n$ 可以根据唯一分解定理分解为 $n = p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}$（其中 $p_i$ 为素数，$a_i$ 为正整数），则欧拉函数的计算公式为： $\varphi(n)=n\prod_{i = 1}^{k}(1-\frac{1}{p_{i}})$ Python 代码实现 ```python def euler_phi(n): result = n p = 2 # 从 2 开始遍历到 sqrt(n) while p * p <= n: if n % p == 0: # 如果 p 是 n 的质因数 while n % p == 0: n //= p # 根据欧拉函数公式更新结果 result = result * (p - 1) // p p += 1 # 如果 n 大于 1，说明 n 本身是一个质数 if n > 1: result = result * (n - 1) // n return result # 读取输入 n = int(input()) # 计算并输出结果 print(euler_phi(n)) ``` 代码解释 1. 初始化结果：将结果初始化为 $n$。 2. 遍历质因数：从 $2$ 开始遍历到 $\sqrt{n}$，如果 $p$ 是 $n$ 的质因数，将 $n$ 中所有的 $p$ 因子除掉，并根据欧拉函数公式更新结果。 3. 处理剩余的质因数：如果遍历完后 $n$ 仍然大于 $1$，说明 $n$ 本身是一个质数，需要再次更新结果。 4. 返回结果：返回最终的欧拉函数值。 复杂度分析 - 时间复杂度：$O(\sqrt{n})$，主要是因为需要遍历到 $\sqrt{n}$ 来寻找质因数。 - 空间复杂度：$O(1)$，只需要常数级的额外空间。 ######[AI问答 | 513点数解答 | 2026-01-25 09:47:10]