给定一个正整数 ，求  中每个数的欧拉函数之和。 输入 共一行，包含一个整数 。 数据范围： 输出 共一行，包含一个整数，表示  中每个数的欧拉函数之和。 样例输入 复制 6 样例输出 复制 12<math xmlns="http://www.w3.org/1998/Math/MathML"> <mn>1</mn> <mo>&lt;=</mo> <mi>n</mi> <mo>&lt;=</mo> <msup> <mn>10</mn> <mn>6</mn> </msup> </math>

思路分析 欧拉函数 $\varphi(n)$ 表示小于等于 $n$ 且与 $n$ 互质的正整数的个数。要求 $1$ 到 $n$ 中每个数的欧拉函数之和，可以先使用线性筛法求出 $1$ 到 $n$ 每个数的欧拉函数值，再将这些值累加起来。 代码实现 以下是使用 Python 实现的代码： ```python n = int(input()) # 初始化欧拉函数数组 phi = [i for i in range(n + 1)] # 标记数组，用于筛法 is_prime = [True] * (n + 1) # 质数列表 primes = [] # 线性筛法求欧拉函数 for i in range(2, n + 1): if is_prime[i]: primes.append(i) phi[i] = i - 1 for prime in primes: if i * prime > n: break is_prime[i * prime] = False if i % prime == 0: phi[i * prime] = phi[i] * prime break phi[i * prime] = phi[i] * (prime - 1) # 计算欧拉函数之和 result = sum(phi[1:]) print(result) ``` 代码解释 1. 初始化： - `phi` 数组用于存储每个数的欧拉函数值，初始值为其本身。 - `is_prime` 数组用于标记每个数是否为质数，初始值都为 `True`。 - `primes` 列表用于存储质数。 2. 线性筛法求欧拉函数： - 遍历从 $2$ 到 $n$ 的每个数 $i$。 - 如果 $i$ 是质数，将其加入 `primes` 列表，并更新 $\varphi(i)=i - 1$。 - 对于每个质数 `prime`，标记 $i\times prime$ 为非质数。 - 如果 $i$ 能被 `prime` 整除，更新 $\varphi(i\times prime)=\varphi(i)\times prime$。 - 否则，更新 $\varphi(i\times prime)=\varphi(i)\times(prime - 1)$。 3. 计算欧拉函数之和： - 将 `phi` 数组中从 $1$ 到 $n$ 的值累加起来，得到最终结果。 复杂度分析 - 时间复杂度：$O(n)$，主要是线性筛法的时间复杂度。 - 空间复杂度：$O(n)$，主要用于存储欧拉函数值和标记数组。 [2026-01-25 09:48:21 | AI问答 | 603点数解答]