1. 项目概述：从一道算法题看数论与编程的深度结合
最近在Acwing平台上刷题，遇到了这道“874. 筛法求欧拉函数”。乍一看标题，它融合了“筛法”、“欧拉函数”、“分解质因数”和“Java实现”几个关键词，这几乎是算法竞赛和面试中数论部分的经典组合拳。很多朋友，尤其是刚接触数论或者正在准备面试的同学，看到这几个词可能就有点发怵，觉得概念抽象，代码实现起来更是无从下手。其实，这道题是一个绝佳的切入点，它能帮你把离散的数学知识点串联成一个有逻辑、可实操的完整知识体系。我花了些时间，不仅把题目AC了，更把背后的原理、不同解法的优劣以及Java实现中的各种细节坑点都梳理了一遍。今天，我就从一个一线开发者的角度，跟你聊聊怎么吃透这道题，以及它背后更广阔的编程思维。
简单来说，这道题的核心任务是：给定一个正整数 n，你需要求出 1 到 n 中每个数的欧拉函数值 φ(i) 的总和。欧拉函数 φ(n) 表示的是小于等于 n 的正整数中，与 n 互质的数的个数。例如，φ(6) = 2，因为1和5与6互质。如果对每个数都单独用分解质因数的方法去求欧拉函数，时间复杂度是 O(n√n)，当 n 达到百万级别时必然超时。因此，题目名中的“筛法”二字就是破题关键，它要求我们利用类似埃氏筛或线性筛的思路，在 O(n) 的时间复杂度内一次性求出1到n所有数的欧拉函数值。这对于正在学习Acwing算法基础课，或者备战Java面试（尤其是那些会问到底层算法和数学思维的岗位）的朋友来说，是一个必须掌握的硬核技能点。
2. 核心思路拆解：为什么“筛法”是唯一正解？
要理解为什么必须用筛法，我们得先看看“暴力解法”为什么行不通。最直观的想法是：遍历1到n，对每个数i，调用一个函数getPhi(i)来计算其欧拉函数。getPhi函数的常规实现就是基于算术基本定理进行分解质因数：将 i 分解为 p1^a1 * p2^a2 * ... * pk^ak 的形式，然后套用公式 φ(i) = i * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)。分解质因数本身需要 O(√i) 的时间。那么，总的时间复杂度就是 O(∑√i)，i从1到n，这个求和大约与 O(n√n) 同阶。当 n=10^6 时，操作次数大概在10^9量级，这在常规的1秒时限内是无法完成的。
注意：这里就是算法题中常见的性能陷阱。很多同学在本地用小数据测试（比如n=100）完全正确，一提交就超时，问题往往就出在对时间复杂度的估算失误上。养成在编码前先进行理论复杂度分析的习惯至关重要。
那么，“筛法”是如何将复杂度降为 O(n) 的呢？其核心思想是“空间换时间”和“利用已计算结果”。我们不再孤立地计算每个 φ(i)，而是在一个循环中，借助数学上欧拉函数的性质，动态地推导出后续的 φ 值。这类似于动态规划中的状态转移。具体来说，我们准备一个长度为 n+1 的数组phi[]，phi[i]最终存储的就是 φ(i) 的值。算法的骨架是一个从2遍历到n的循环，在循环体中，我们根据当前数 i 是质数还是合数，以及其最小质因子，来决定如何更新phi[i]以及利用 i 去更新它的倍数们的phi值。这个过程确保了每个数 φ 值只被计算一次，从而实现了线性时间复杂度。
3. 数学原理与公式推导：欧拉函数的三个关键性质
任何高效的算法都建立在坚实的数学基础之上。要实现上述筛法，我们需要深刻理解并应用欧拉函数的以下几个性质。这些性质不仅是解题的钥匙，也是面试中面试官可能深挖的点。
性质一：若 n 是质数 p，则 φ(p) = p - 1。这个很好理解，因为质数 p 与所有小于它的正整数都互质。
性质二：若 n 是质数 p 的 k 次幂，即 n = p^k，则 φ(p^k) = p^k - p^(k-1) = p^k * (1 - 1/p)。在 1 到 p^k 这些数中，只有那些包含质因子 p 的数才与 p^k 不互质。这些数分别是 p, 2p, 3p, ..., p^(k-1) * p，总共有 p^(k-1) 个。所以互质的数就有 p^k - p^(k-1) 个。
性质三（积性函数性质）：若 a 与 b 互质，则 φ(a*b) = φ(a) * φ(b)。这是一个非常强大的性质。但更关键的是，在筛法中，我们更多用到的是它的一个“不完全积性”的推论，来处理 a 与 b 不互质的情况。
推导筛法的核心递推关系：假设我们有一个合数 n，它的最小质因子是 p，那么我们可以将 n 写成 n = p * m。 此时，m 可能包含质因子 p，也可能不包含。这引出了两种情况：
情况一：p 能整除 m (即 m % p == 0)。这意味着 m 包含了质因子 p，所以 n 和 m 含有相同的质因子集合。设 m = p^k * t，其中 t 与 p 互质，那么 n = p^(k+1) * t。 根据性质二：φ(n) = n * (1 - 1/p) = p * m * (1 - 1/p) = p * φ(m)。 因为 φ(m) = m * (1 - 1/p) * ...，而 n 只是比 m 多乘了一个 p，且质因子集合未变，所以 φ(n) = p * φ(m)。
情况二：p 不能整除 m (即 m % p != 0)。这意味着 p 是 n 独有的最小质因子，m 与 p 互质。 根据性质三（积性）：φ(n) = φ(p) * φ(m) = (p - 1) * φ(m)。
这两个递推公式，就是线性筛法求欧拉函数的灵魂。我们只需要知道一个数的最小质因子，以及它除以这个最小质因子后的结果 m 的 φ 值，就可以在 O(1) 时间内求出这个数的 φ 值。
4. 算法实现详解：线性筛法模板与Java代码逐行解析
理解了数学原理，我们来看代码实现。这里我提供两个版本的Java实现：一个是易于理解的埃氏筛思想改进版，另一个是效率最高的线性筛（欧拉筛）标准模板。我会重点讲解后者，因为它是面试和竞赛中的首选。
4.1 基础准备：变量与数组定义
首先，无论哪种筛法，我们都需要一些公共的辅助数据结构。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // phi[i] 表示 φ(i) int[] phi = new int[n + 1]; // primes[] 用于存储筛选出来的所有质数 int[] primes = new int[n + 1]; // cnt 是质数计数器 int cnt = 0; // st[i] 为 false 表示 i 是质数，为 true 表示 i 是合数（已被筛掉） boolean[] st = new boolean[n + 1]; // 初始化：φ(1) = 1，这是一个特例 phi[1] = 1; // ... 筛法核心逻辑将放在这里 // 计算总和 long res = 0; for (int i = 1; i <= n; i++) { res += phi[i]; } System.out.println(res); } }关键点解析：
phi[1] = 1是定义。虽然1与自身互质，但欧拉函数通常定义 φ(1)=1，这样能保证积性函数性质在边界上也成立。- 使用
long类型存储结果res非常重要。因为当 n 较大时，φ(i) 的总和可能超出 int 的范围（例如 n=10^6 时总和已经很大）。这是Java实现中一个常见的坑点，容易导致结果错误。
4.2 核心逻辑：线性筛法求欧拉函数
现在，我们把筛法的核心循环填入。这段代码将同时完成两件事：筛选出所有质数，并计算出每个数的欧拉函数。
// 从2开始遍历到n for (int i = 2; i <= n; i++) { // 如果 i 是质数 if (!st[i]) { primes[cnt++] = i; // 将质数 i 存入数组 phi[i] = i - 1; // 性质一：质数的欧拉函数值为 i-1 } // 用当前已得到的质数 primes[j] 去筛它的倍数 // 关键：无论 i 是质数还是合数，都会执行这一步 for (int j = 0; primes[j] <= n / i; j++) { st[primes[j] * i] = true; // 标记合数 primes[j] * i // 情况判断：这是递推公式应用的地方 if (i % primes[j] == 0) { // 情况一：primes[j] 是 i 的最小质因子 // 此时 primes[j] * i 的最小质因子也是 primes[j] // 根据推导公式：φ(primes[j] * i) = primes[j] * φ(i) phi[primes[j] * i] = primes[j] * phi[i]; break; // 核心：保证每个合数只被其最小质因子筛掉一次 } else { // 情况二：primes[j] 不是 i 的质因子（即与 i 互质） // 根据推导公式：φ(primes[j] * i) = (primes[j] - 1) * φ(i) phi[primes[j] * i] = (primes[j] - 1) * phi[i]; } } }逐行拆解与心法：
if (!st[i])：如果i未被标记为合数，那么它一定是质数。这是线性筛的起点。phi[i] = i - 1：对质数直接应用性质一。- 内层循环
for (int j = 0; primes[j] <= n / i; j++)：用当前已知的所有质数primes[j]去尝试标记合数primes[j] * i。条件primes[j] <= n / i是为了防止primes[j] * i超过数组范围 n，是防越界的经典写法。 st[primes[j] * i] = true：标记primes[j] * i为合数。if (i % primes[j] == 0)：这是整个算法的灵魂所在。它判断质数primes[j]是否是i的因子。- 如果成立：说明
primes[j]是i的最小质因子（因为我们是按顺序用质数去试的，第一个能整除i的primes[j]一定是最小质因子）。此时，primes[j] * i这个数的最小质因子也是primes[j]。对应我们之前推导的“情况一”，所以φ(primes[j] * i) = primes[j] * φ(i)。紧接着的break语句至关重要，它保证了每个合数只会被它的最小质因子筛掉一次。例如，当i=4,primes[j]=2时，标记了4*2=8后立即break。如果不break，当j继续增加到primes[j]=3时，会标记4*3=12，而12的最小质因子是2，本应由i=6时用primes[j]=2来筛，这就造成了重复标记，破坏了线性复杂度。 - 如果不成立：说明
primes[j]比i的最小质因子还要小，且与i互质。对应“情况二”，所以φ(primes[j] * i) = (primes[j] - 1) * φ(i)。
- 如果成立：说明
实操心得：这个
break是线性筛区别于埃氏筛的核心，也是保证 O(n) 时间复杂度的关键。很多同学在记忆模板时容易忘记它，导致算法退化。你可以这样理解：i就像是一个“搬运工”，它只负责用比它自身最小质因子更小或相等的质数（primes[j]）去制造合数。一旦遇到自己的最小质因子，任务就完成了，立即休息（break），把制造包含这个质因子的更大合数的任务，留给后面更大的i去做。
4.3 算法流程模拟：以 n=10 为例
为了加深理解，我们手动模拟一下 n=10 的过程，重点关注phi[]数组的变化。
| i | st[i] | 质数判断 | primes[] | 内层循环 (primes[j]) | 标记的合数 | phi[合数] 计算逻辑 | phi[] 数组更新 (下标:值) |
|---|---|---|---|---|---|---|---|
| 2 | false | 是质数 | [2] | j=0, pj=2 | 4 | i%pj=2%2=0 -> φ(4)=2φ(2)=21=2 | phi[2]=1, phi[4]=2 |
| phi[2]=1 | break | ||||||
| 3 | false | 是质数 | [2,3] | j=0, pj=2 | 6 | i%pj=3%2!=0 -> φ(6)=1φ(3)=12=2 | phi[3]=2, phi[6]=2 |
| phi[3]=2 | j=1, pj=3 | 9 | i%pj=3%3=0 -> φ(9)=3φ(3)=32=6 | phi[9]=6, break | |||
| 4 | true | 是合数 (已标记) | [2,3] | j=0, pj=2 | 8 | i%pj=4%2=0 -> φ(8)=2φ(4)=22=4 | phi[8]=4, break |
| 5 | false | 是质数 | [2,3,5] | j=0, pj=2 | 10 | i%pj=5%2!=0 -> φ(10)=1φ(5)=14=4 | phi[5]=4, phi[10]=4 |
| phi[5]=4 | j=1, pj=3 | 15>10 停止 | |||||
| 6 | true | 是合数 | [2,3,5] | j=0, pj=2 | 12>10 停止 | i%pj=6%2=0 -> φ(12)=2φ(6)=22=4 | phi[12] 在本次循环不会计算，因为12>10 |
| break | |||||||
| 7 | false | 是质数 (但循环已到7) | [2,3,5,7] | j=0, pj=2 | 14>10 停止 | phi[7]=6 | |
| ... | ... | ... | ... | ... | ... | ... | ... |
最终，我们得到 phi[1]=1, phi[2]=1, phi[3]=2, phi[4]=2, phi[5]=4, phi[6]=2, phi[7]=6, phi[8]=4, phi[9]=6, phi[10]=4。求和结果为 1+1+2+2+4+2+6+4+6+4 = 32。
通过这个表格，你可以清晰地看到每个phi值是如何被递推出来的，以及break如何控制每个合数只被计算一次。
5. 性能对比与算法选择：线性筛为何是终极答案？
在解决这个问题时，你可能会想到几种不同的筛法。我们来对比一下，为什么线性筛是最优解。
1. 埃拉托斯特尼筛法（埃氏筛）的朴素改造：一种思路是先用埃氏筛出所有质数，然后再遍历1到n，对每个数用质数表去分解质因数并套公式计算 φ。这样做的时间复杂度是 O(n log log n)（筛法） + O(n * (质因数个数))（计算φ），后者在平均情况下接近 O(n log n)，比线性筛差。而且实现起来需要两个步骤，代码更复杂。
2. 基于埃氏筛思想的欧拉函数计算：我们可以模仿埃氏筛的过程，初始化一个phi[i] = i的数组。然后遍历所有质数 p，对于 p 的所有倍数i，执行phi[i] = phi[i] / p * (p-1)。这相当于在筛除合数的同时，应用欧拉函数公式φ(n) = n * Π(1 - 1/p)。这种方法的时间复杂度是 O(n log log n)，比线性筛的 O(n) 略差，但代码非常简洁易懂，对于 n 在 10^7 以内的问题通常也足够快。其代码骨架如下：
// 初始化 for (int i = 1; i <= n; i++) phi[i] = i; // 筛法 for (int i = 2; i <= n; i++) { if (phi[i] == i) { // i是质数 for (int j = i; j <= n; j += i) { phi[j] = phi[j] / i * (i - 1); } } }3. 线性筛（欧拉筛）：正如我们上面详细实现的，时间复杂度是严格的 O(n)。它是理论上的最优解，尤其是在对性能要求极端苛刻（如 n 接近 10^7）的场景下。虽然代码比上一种方法稍复杂，但它是标准的模板，一旦掌握，可以解决一系列类似问题（如求莫比乌斯函数、约数个数等）。
选择建议：
- 面试与竞赛：无脑选择线性筛模板。它展示了你对算法最优解的追求和对数论性质的深刻理解。
- 快速实现与理解：如果时间紧迫，或者 n 不是特别大，基于埃氏筛思想的第二种方法也是很好的选择，代码简单不易错。
- 个人学习：建议两种都实现一遍，对比理解其内在联系与差异，这对巩固知识大有裨益。
6. Java实现中的常见“坑”与调试技巧
即便理解了算法，用Java实现时还是会遇到一些语言和细节特有的问题。下面是我在多次实现和教学中总结出的常见“坑点”。
坑点一：数组越界与循环条件内层循环的结束条件primes[j] <= n / i是精髓。绝对不能写成primes[j] * i <= n，因为当i很大时，primes[j] * i可能超过int范围，导致溢出变成负数，从而使循环条件误判，引发数组越界异常ArrayIndexOutOfBoundsException。使用除法判断是安全的惯用写法。
坑点二：结果溢出这是最容易被忽略的一点。phi[i]本身是int，但1到n的总和可能非常大。当 n=10^6 时，总和已经达到约 3e11 的数量级，远超int的表示范围 (约2e9)。因此，存储总和的变量res必须使用long类型。
坑点三：初始化与边界条件
phi[1] = 1必须设置。有些推导中 φ(1) 可能被视为0或不定义，但在这个求和问题中，约定俗成 φ(1)=1，且这样能保证递推公式在边界情况下的正确性。- 质数数组
primes的大小设为n+1是安全的，因为1到n之间质数的数量肯定小于n。 - 布尔数组
st默认值为false，表示都是质数，我们从2开始筛。
坑点四：break语句的遗忘如前所述，忘记在内层循环中添加if (i % primes[j] == 0)后的break语句，会使算法退化为近似 O(n log n) 的复杂度，在 n 较大时可能导致超时。这是一个非常隐蔽的错误，因为对于小数据它依然能得出正确结果。
调试技巧：
- 小数据验证：首先用 n=1, 2, 3, 6, 10 这样的小数据手动计算，与程序输出对比。可以单独写一个
getPhi函数用于暴力验证。 - 打印中间变量：在循环中打印
i,primes[j],phi[primes[j]*i]等值，对照我们上面的模拟表格，看每一步的计算是否符合预期。 - 性能测试：用 n=10^6 测试，在线性筛下应该在百毫秒级别完成。如果明显变慢，检查是否是
break遗漏导致产生了大量重复标记。
7. 从模板到精通：举一反三与面试扩展
掌握这道题，绝不仅仅是为了AC一道题。它为你打开了一扇门，门后是算法竞赛和高级面试中常见的“积性函数线性筛”问题家族。
变体一：求莫比乌斯函数 μ(n)莫比乌斯函数 μ(n) 也是一个积性函数，其定义略复杂，但也可以用线性筛在 O(n) 时间内求出。核心递推关系与欧拉函数类似：
- 若 n 是质数，μ(n) = -1。
- 在筛的过程中，对于
i * primes[j]：- 若
i % primes[j] == 0，则μ(i * primes[j]) = 0（因为包含了平方因子）。 - 否则，
μ(i * primes[j]) = -μ(i)。 你可以尝试基于欧拉筛的框架，修改几行代码来实现它。
- 若
变体二：求约数个数函数 d(n) 或约数和函数 σ(n)这两个也是积性函数。求约数个数需要额外维护一个数组minp_cnt[]记录每个数最小质因子的次数。思路是：
- 若
i是质数，d(i)=2,minp_cnt[i]=1。 - 对于
i * primes[j]：- 若
i % primes[j] == 0，则minp_cnt[i * primes[j]] = minp_cnt[i] + 1，且d(i * primes[j]) = d(i) / (minp_cnt[i] + 1) * (minp_cnt[i] + 2)。 - 否则，
minp_cnt[i * primes[j]] = 1，且d(i * primes[j]) = d(i) * 2。 约数和函数的筛法思路类似，但需要维护两个数组。
- 若
面试扩展点：在技术面试中，面试官可能不会直接让你写代码，但可能会围绕这些知识点提问：
- “如何快速判断一个数是否是质数？”你可以从试除法讲到 Miller-Rabin 概率算法。
- “如何求一个大数的欧拉函数值？（比如一个50位的数）”这时筛法就无能为力了，你需要回到“分解质因数”这个基本方法，并可以提到 Pollard-Rho 这样的高效大数分解算法。
- “欧拉定理是什么？在RSA加密中如何应用？”这道题是理解欧拉定理（a^φ(n) ≡ 1 (mod n)，当a与n互质）的基础。RSA加密的核心计算之一就是利用欧拉函数来生成私钥。
- “除了欧拉函数，还有哪些常见的积性函数？它们有什么性质？”你可以列举出上面提到的莫比乌斯函数、约数个数、约数和，以及常值函数、单位函数等，并说明积性函数在狄利克雷卷积下的良好性质。
8. 工程实践中的思考：超越刷题
最后，我想跳出这道题本身，谈点工程上的思考。我们学习这些精妙的算法，最终是为了解决实际问题。
在真实的业务系统中，你几乎不会遇到需要一次性计算前一百万个欧拉函数值的场景。但是，这种“预处理+查表”的思想，以及“用空间换时间”的优化策略，却是无处不在的。例如：
- 缓存（Cache）：数据库查询缓存、CPU多级缓存、Redis缓存，其本质都是预先计算或存储可能被重复使用的数据，避免昂贵的重复计算或IO操作。
- 动态规划（DP）：和线性筛的思想高度一致，都是定义状态，找到状态转移方程，然后以正确的顺序填充一张表，确保每个状态只被计算一次。
- 搜索引擎的倒排索引：可以看作是对海量文档的一种“预处理”，以便在查询时能够快速响应。
这道题更重要的价值在于训练一种思维：面对一个需要重复计算的问题，能否找到计算之间的内在联系（递推关系），从而设计出一种批量、高效的计算方法？这种化繁为简、构建系统的能力，才是算法学习带给我们的长期收益。
所以，下次当你再看到“筛法求欧拉函数”时，希望你不只看到一段需要记忆的模板代码，而是看到一个融合了数论之美、算法之巧和工程之用的经典案例。理解它，掌握它，然后尝试去解决下一个更复杂的问题，这才是学习的正循环。
