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

你描述的应该是欧拉函数。欧拉函数 $\varphi(n)$ 表示小于或等于正整数 $n$ 的数中与 $n$ 互质的数的个数。 欧拉函数的计算公式 如果将正整数 $n$ 分解质因数为 $n = p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}$，那么欧拉函数 $\varphi(n)=n\prod_{i = 1}^{k}(1-\frac{1}{p_{i}})$。 Python 代码实现 ```python def euler_phi(n): result = n p = 2 # 对 n 进行质因数分解 while p * p <= n: if n % p == 0: # 根据欧拉函数公式更新结果 result = result // p * (p - 1) while n % p == 0: n = n // p p = p + 1 # 如果 n 仍然大于 1，说明 n 本身是一个质数 if n > 1: result = result // n * (n - 1) return result # 读取输入 n = int(input()) # 计算并输出欧拉函数值 print(euler_phi(n)) ``` 代码解释 1. 函数 `euler_phi`：该函数接受一个正整数 `n` 作为参数，用于计算 $\varphi(n)$。 2. 质因数分解：从 $2$ 开始尝试对 $n$ 进行质因数分解，对于每个质因数 $p$，根据欧拉函数公式更新结果。 3. 处理剩余的质数：如果在质因数分解结束后，$n$ 仍然大于 $1$，说明 $n$ 本身是一个质数，需要再次更新结果。 4. 主程序：读取输入的正整数 $n$，调用 `euler_phi` 函数计算 $\varphi(n)$ 并输出结果。 复杂度分析 - 时间复杂度：$O(\sqrt{n})$，主要是因为质因数分解的时间复杂度为 $O(\sqrt{n})$。 - 空间复杂度：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 514点数解答 | 2026-01-25 20:58:39]