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) 同阶。当 n10^6 时操作次数大概在10^9量级这在常规的1秒时限内是无法完成的。注意这里就是算法题中常见的性能陷阱。很多同学在本地用小数据测试比如n100完全正确一提交就超时问题往往就出在对时间复杂度的估算失误上。养成在编码前先进行理论复杂度分析的习惯至关重要。那么“筛法”是如何将复杂度降为 O(n) 的呢其核心思想是“空间换时间”和“利用已计算结果”。我们不再孤立地计算每个 φ(i)而是在一个循环中借助数学上欧拉函数的性质动态地推导出后续的 φ 值。这类似于动态规划中的状态转移。具体来说我们准备一个长度为 n1 的数组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^(k1) * 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 的范围例如 n10^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语句至关重要它保证了每个合数只会被它的最小质因子筛掉一次。例如当i4,primes[j]2时标记了4*28后立即break。如果不break当j继续增加到primes[j]3时会标记4*312而12的最小质因子是2本应由i6时用primes[j]2来筛这就造成了重复标记破坏了线性复杂度。如果不成立说明primes[j]比i的最小质因子还要小且与i互质。对应“情况二”所以φ(primes[j] * i) (primes[j] - 1) * φ(i)。实操心得这个break是线性筛区别于埃氏筛的核心也是保证 O(n) 时间复杂度的关键。很多同学在记忆模板时容易忘记它导致算法退化。你可以这样理解i就像是一个“搬运工”它只负责用比它自身最小质因子更小或相等的质数primes[j]去制造合数。一旦遇到自己的最小质因子任务就完成了立即休息break把制造包含这个质因子的更大合数的任务留给后面更大的i去做。4.3 算法流程模拟以 n10 为例为了加深理解我们手动模拟一下 n10 的过程重点关注phi[]数组的变化。ist[i]质数判断primes[]内层循环 (primes[j])标记的合数phi[合数] 计算逻辑phi[] 数组更新 (下标:值)2false是质数[2]j0, pj24i%pj2%20 - φ(4)2φ(2)212phi[2]1, phi[4]2phi[2]1break3false是质数[2,3]j0, pj26i%pj3%2!0 - φ(6)1φ(3)122phi[3]2, phi[6]2phi[3]2j1, pj39i%pj3%30 - φ(9)3φ(3)326phi[9]6, break4true是合数 (已标记)[2,3]j0, pj28i%pj4%20 - φ(8)2φ(4)224phi[8]4, break5false是质数[2,3,5]j0, pj210i%pj5%2!0 - φ(10)1φ(5)144phi[5]4, phi[10]4phi[5]4j1, pj31510 停止6true是合数[2,3,5]j0, pj21210 停止i%pj6%20 - φ(12)2φ(6)224phi[12] 在本次循环不会计算因为1210break7false是质数 (但循环已到7)[2,3,5,7]j0, pj21410 停止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。求和结果为 1122426464 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的总和可能非常大。当 n10^6 时总和已经达到约 3e11 的数量级远超int的表示范围 (约2e9)。因此存储总和的变量res必须使用long类型。坑点三初始化与边界条件phi[1] 1必须设置。有些推导中 φ(1) 可能被视为0或不定义但在这个求和问题中约定俗成 φ(1)1且这样能保证递推公式在边界情况下的正确性。质数数组primes的大小设为n1是安全的因为1到n之间质数的数量肯定小于n。布尔数组st默认值为false表示都是质数我们从2开始筛。坑点四break语句的遗忘如前所述忘记在内层循环中添加if (i % primes[j] 0)后的break语句会使算法退化为近似 O(n log n) 的复杂度在 n 较大时可能导致超时。这是一个非常隐蔽的错误因为对于小数据它依然能得出正确结果。调试技巧小数据验证首先用 n1, 2, 3, 6, 10 这样的小数据手动计算与程序输出对比。可以单独写一个getPhi函数用于暴力验证。打印中间变量在循环中打印i,primes[j],phi[primes[j]*i]等值对照我们上面的模拟表格看每一步的计算是否符合预期。性能测试用 n10^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和线性筛的思想高度一致都是定义状态找到状态转移方程然后以正确的顺序填充一张表确保每个状态只被计算一次。搜索引擎的倒排索引可以看作是对海量文档的一种“预处理”以便在查询时能够快速响应。这道题更重要的价值在于训练一种思维面对一个需要重复计算的问题能否找到计算之间的内在联系递推关系从而设计出一种批量、高效的计算方法这种化繁为简、构建系统的能力才是算法学习带给我们的长期收益。所以下次当你再看到“筛法求欧拉函数”时希望你不只看到一段需要记忆的模板代码而是看到一个融合了数论之美、算法之巧和工程之用的经典案例。理解它掌握它然后尝试去解决下一个更复杂的问题这才是学习的正循环。