线性筛法高效计算欧拉函数：从原理到实战应用

1. 项目概述：从“亲戚”到数论，一个经典问题的深度剖析

看到“Relatives”这个标题，你可能会联想到人际关系或家庭伦理。但在算法竞赛和数论领域，这其实是一个相当经典的题目，它考察的核心是欧拉函数的计算。题目通常这样描述：给定一个正整数N，求小于N且与N互质的正整数的个数。这个“互质”的关系，就像数字之间的“亲戚”关系——没有大于1的公共因子，彼此“最简”。所以，题目“Relatives”的本质，就是计算欧拉函数 φ(N) 的值。

为什么这个问题如此重要？在公钥加密体系（如RSA）、随机数生成、乃至一些组合数学问题中，快速计算一个数的欧拉函数值是基础操作。暴力遍历检查每个数是否与N互质，时间复杂度是O(N log N)，当N达到10^9甚至更大时完全不可行。这就需要我们搬出数论中的利器：素数筛法结合欧拉函数的性质。本文将彻底拆解这个“素数筛+欧拉函数”的组合拳，不仅告诉你如何做，更深入剖析每一步背后的数学原理和工程化实现的精妙之处。无论你是正在备战算法竞赛的选手，还是对基础数论感兴趣的程序员，这篇从实战中总结的干货都能让你透彻理解并熟练应用。

2. 核心思路与数学原理拆解

2.1 欧拉函数定义与基础性质

欧拉函数 φ(n)，定义为小于等于n的正整数中与n互质的数的个数。几个关键性质是我们算法的基石：

1. 积性函数性质：如果两个正整数a和b互质（gcd(a, b)=1），那么 φ(a*b) = φ(a) * φ(b)。这是我们将大问题分解为小问题的关键。
2. 质数幂次公式：若p是一个质数，则 φ(p^k) = p^k - p^(k-1) = p^(k-1) * (p - 1)。这给出了对单个质因数幂次的计算方法。
3. 通用计算公式：若n的标准分解式为 n = p1^k1 * p2^k2 * ... * pm^km，其中pi为质数，则根据积性，有： φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm) 这个公式直观地反映了“剔除非互质数”的过程：减去所有是p1倍数的数，但这样会重复减去同时是p1和p2倍数的数（即p1*p2的倍数）……最终用容斥原理导出了这个连乘形式。

基于通用公式，一个最直接的算法思路就出来了：对N进行质因数分解，得到所有不同的质因数p，然后套用公式计算。这个算法的时间复杂度主要取决于质因数分解的速度。对于单个N，试除法分解的复杂度是O(√N)。这在很多情况下已经足够好，但当我们遇到需要预处理一段区间内所有数的欧拉函数值时（例如求解N个查询，或者需要用到区间内所有φ值进行后续计算），就需要更高效的批量处理方法。这时，“素数筛+欧拉函数”的联动就登场了。

2.2 素数筛法选型：为什么是线性筛？

素数筛法的目标是以低于逐个判断的方式，高效标记出一段区间内的所有质数。常见的筛法有：

• 埃拉托斯特尼筛法：从2开始，将每个质数的倍数标记为合数。时间复杂度约为O(n log log n)。在标记合数的过程中，我们其实已经知道了每个数的一个质因数（即标记它的那个质数）。利用这个信息，我们可以在筛的同时递推计算欧拉函数值，这就是“欧拉筛”的一种实现。但埃氏筛的一个小缺点是，一个合数可能被多个质数重复标记（例如6会被2和3都标记），这在递推φ值时需要小心处理逻辑。
• 线性筛：也称为欧拉筛，其核心思想是确保每个合数只被其最小的质因数筛掉一次。这带来了O(n)的线性时间复杂度。正是这个“每个合数只被最小质因数筛一次”的特性，使得我们可以在筛的过程中，根据当前数与质数的关系，以O(1)的代价递推计算出每个数的φ值，完美匹配了欧拉函数的积性性质。

注意：这里的“欧拉筛”指的是线性时间复杂度的素数筛法，与我们要求解的“欧拉函数”是两回事，只是都冠以欧拉之名。线性筛是实现批量计算欧拉函数最高效的载体。

选择线性筛的理由：

1. 效率最高：O(n)的预处理时间复杂度，使得后续查询每个数的φ值都是O(1)。
2. 逻辑清晰：筛法过程与φ值递推过程可以紧密耦合，代码简洁优雅。
3. 一石二鸟：一次预处理，同时得到了区间内所有质数列表和所有数的欧拉函数值，性价比极高。

因此，在“Relatives”这类问题需要处理大量数据或区间查询时，线性筛是预处理阶段不二的选择。接下来，我们就深入线性筛的内部，看它如何与欧拉函数的计算完美融合。

3. 算法核心：线性筛中递推欧拉函数

这是整个实现中最精妙的部分。我们目标是得到一个数组phi[]，其中phi[i]存储整数 i 的欧拉函数值。同时，我们维护一个质数列表primes和一个布尔数组isPrime[]来标记是否质数。

3.1 递推的初始状态与边界

首先设定边界：

• phi[1] = 1。根据定义，小于等于1且与1互质的数只有1本身。
• 对于任意质数p：phi[p] = p - 1。因为1到p-1的所有数都与质数p互质。

在线性筛的主循环中，我们遍历区间内的每一个整数i（从2开始）。

3.2 递推关系的三种情况

假设当前遍历到整数i，我们用它来筛掉后续的合数。对于质数列表primes中的每一个质数primes[j]（记为p），我们标记合数i * p。在标记的同时，根据i和p的关系，决定如何计算phi[i * p]。这里分三种情况，是理解算法的关键：

情况一：i % p == 0(即p整除i)这意味着p是i的一个质因数。设i = p^k * m，其中m与p互质。 那么i * p = p^(k+1) * m。 根据欧拉函数公式：φ(i * p) = (i * p) * (1 - 1/p) * (其他与m相关的连乘部分)而φ(i) = i * (1 - 1/p) * (其他与m相关的连乘部分)对比两式，可以发现φ(i * p) = p * φ(i)。直观理解：i已经包含了质因数p，i*p只是增加了p的指数，并未引入新的质因数。根据公式，φ(i*p)只是在φ(i)的基础上多乘了一个p（因为n变成了n*p，而连乘部分(1-1/p)已经存在且不变）。

情况二：i % p != 0(即p不整除i)这意味着p是i * p的一个新的质因数，且i与p互质。 由于欧拉函数是积性函数，对于互质的两个数i和p，有：φ(i * p) = φ(i) * φ(p)而φ(p) = p - 1。 所以φ(i * p) = φ(i) * (p - 1)。

情况三：当前数i本身是质数在循环开始时，如果发现i是质数（未被标记），则将其加入质数列表primes，并直接设置phi[i] = i - 1。这是递推的起点。

3.3 算法流程与代码骨架

结合以上递推关系，我们可以写出完整的预处理函数。以下以C++为例，展示核心代码逻辑并附详细注释。

#include <vector> using namespace std; const int MAX_N = 1000000; // 预处理的上限 vector<int> primes; // 存储所有筛出的质数 bool isPrime[MAX_N + 1]; // 标记数组，默认应初始化为true int phi[MAX_N + 1]; // 存储欧拉函数值 void linear_sieve_phi(int n) { // 初始化 fill(isPrime, isPrime + n + 1, true); primes.clear(); phi[1] = 1; // 边界条件 for (int i = 2; i <= n; ++i) { if (isPrime[i]) { primes.push_back(i); phi[i] = i - 1; // 情况三：i是质数 } // 用当前数i和已知质数筛合数 for (int j = 0; j < primes.size(); ++j) { long long nextNum = 1LL * i * primes[j]; // 防止溢出 if (nextNum > n) break; // 超过范围，退出内层循环 isPrime[nextNum] = false; // 标记合数 // 关键递推部分 if (i % primes[j] == 0) { // 情况一：primes[j]是i的质因数 phi[nextNum] = phi[i] * primes[j]; break; // 线性筛的精髓：保证每个合数只被最小质因数筛一次 } else { // 情况二：primes[j]与i互质 phi[nextNum] = phi[i] * (primes[j] - 1); } } } }

实操心得：代码中if (nextNum > n) break;和if (i % primes[j] == 0) break;这两个break是线性筛效率的保证。前者控制范围，后者确保了“每个合数只被最小质因数筛一次”。当i % primes[j] == 0时，说明primes[j]是i的最小质因数（因为我们是按顺序遍历质数列表），那么对于i的其他质因数primes[k] (k > j)，合数i * primes[k]的最小质因数应该是primes[j]而不是primes[k]，它会在未来i' = i / primes[j] * primes[k]时被primes[j]筛掉。此时跳出循环，避免了重复标记。

4. 针对“Relatives”问题的完整解决方案

有了批量计算欧拉函数的能力，我们来看如何解决原问题。题目输入通常是一个正整数N，输出φ(N)。我们需要根据数据范围选择策略。

4.1 策略一：单次查询，直接质因数分解

如果题目是单次查询，且N非常大（例如达到10^12），预处理整个区间不现实。这时应采用试除法质因数分解结合欧拉函数公式。

步骤：

1. 初始化ans = N。
2. 从p = 2开始，循环直到p * p <= N。
   • 如果N % p == 0，说明p是一个质因数。
   • 执行ans = ans / p * (p - 1)。这等价于ans *= (1 - 1/p)，但避免了浮点数运算。
   • 将N中的所有p因子除尽：while (N % p == 0) N /= p;。
3. 循环结束后，如果N > 1，说明剩下的N本身是一个大于√N的质因数。对ans进行同样的操作：ans = ans / N * (N - 1)。
4. 输出ans。

代码示例：

long long phi_single(long long n) { long long ans = n; long long temp = n; for (long long p = 2; p * p <= temp; ++p) { if (temp % p == 0) { ans = ans / p * (p - 1); // 应用公式 while (temp % p == 0) temp /= p; // 除尽该因子 } } if (temp > 1) { // 处理剩余的大质因子 ans = ans / temp * (temp - 1); } return ans; }

时间复杂度：O(√N)，在可接受范围内。

4.2 策略二：多次查询或区间需求，线性筛预处理

如果题目需要处理多个N（多组测试数据），或者需要输出1到N所有数的φ值，那么预处理是更优解。

步骤：

1. 读取所有查询，找到其中最大的N_max。
2. 调用linear_sieve_phi(N_max)函数，预处理出1到N_max的所有phi值。
3. 对于每个查询N，直接输出phi[N]。

优势：预处理复杂度 O(N_max)，此后每次查询都是 O(1)。当查询数量很多时，平均效率远高于对每个N单独分解。

4.3 策略选择与性能对比

注意事项：选择策略时，务必注意数据范围。如果题目明确N≤10^6且有10^5组数据，那么线性筛预处理是必须的。如果N≤10^12但只有1组数据，试除法则更合适。同时，注意phi[1] = 1这个边界条件在题目中是否有特殊定义（极少数题目可能认为1没有“小于1的正整数”而定义φ(1)=0，但标准定义是1）。

5. 实战演练、调试与边界处理

理论懂了，代码写了，但在实际解题（尤其是线上判题系统）中，还有很多细节坑等着我们。

5.1 典型输入输出处理

“Relatives”类题目的输入输出通常很简单，但要注意：

• 输入可能包含多个测试用例，直到输入0为止。
• N的范围可能从1开始。
• 输出通常就是φ(N)的值。

一个健壮的输入输出框架如下：

#include <iostream> using namespace std; const int MAXN = 1000000; int phi[MAXN + 5]; void init() { // ... 线性筛预处理phi数组的代码 } int main() { init(); // 在程序开始前一次性预处理 int n; while (cin >> n && n != 0) { // 循环读取直到输入0 cout << phi[n] << endl; } return 0; }

5.2 常见“坑点”与调试技巧

1. 整数溢出：在计算i * primes[j]时，即使i和primes[j]都在int范围内，它们的乘积也可能超出int范围，导致溢出成为负数，进而使得数组访问越界或循环判断出错。务必使用long long类型进行中间计算，如long long nextNum = 1LL * i * primes[j];。

2. 数组越界：确保定义的数组大小（如phi[MAX_N+1]）至少比最大N大1，因为我们的下标是从1开始使用的。如果题目说N≤1000000，那么数组大小至少为1000001。

3. 初始化问题：

   • isPrime数组需要初始化为true（可以用fill或memset，注意memset按字节赋值，true的非零值可能被赋为0x01，在bool判断中通常没问题，但更推荐fill）。
   • phi[1] = 1必须在循环开始前设定好。
   • 质数列表primes要记得clear()。

4. 算法逻辑错误：最常见的是递推公式用错。牢记：

   • if (i % p == 0) phi[i*p] = phi[i] * p;
   • else phi[i*p] = phi[i] * (p - 1);可以自己用几个小例子验证，比如计算φ(4)、φ(6)、φ(8)。

5. 多组数据预处理：如果题目没有明确说所有测试用例的N不超过某个值，但时间限制宽松，可以保守地预处理一个较大的范围（如1e6）。如果内存紧张，再考虑用单次分解法。

5.3 性能优化小技巧

• 用数组代替vector：在性能要求极高的竞赛中，有时用静态数组模拟质数列表比vector稍快，因为减少了动态扩容的开销。可以预先估计质数个数（约 n/ln(n)）。
• 位筛法：用bitset存储isPrime信息，可以将空间压缩到原来的1/8，对于超大范围（如1e8）的预处理非常有用，但访问速度可能稍慢。
• 分块筛：当需要计算极大范围（如1e12）的欧拉函数时，内存无法容纳整个phi数组。这时可以使用“分段筛”或“Meissel-Lehmer算法”等更高级的技巧，但这已超出本文基础范围。

6. 从“Relatives”到更广阔的应用

掌握了线性筛求欧拉函数，你解锁的不仅仅是一道题。它是许多数论和组合问题的基石。

6.1 相关变种与扩展问题

1. 区间欧拉函数和：求 ∑φ(i) for i in [L, R]。预处理前缀和即可。
2. 最大公约数之和：求 ∑∑gcd(i, j)。可以通过欧拉函数转化为 ∑ (φ(d) * floor(n/d)^2) 来求解，复杂度大幅降低。
3. 既约分数计数：给定N，求有多少个分数a/b满足0<a<b≤N且a/b是最简分数。这等价于求 ∑φ(i) for i=2 to N。
4. 模n下的乘法逆元：在数论中，若a与n互质，则a在模n下的逆元存在，且为 a^(φ(n)-1) mod n（根据欧拉定理）。快速计算φ(n)是其中的一步。

6.2 算法思想的迁移

线性筛的精髓——“用最小质因数标记合数”——可以推广到计算其他积性数论函数。例如：

• 莫比乌斯函数 μ(n)：同样可以在线性筛中递推。
• 约数个数函数 d(n)和约数和函数 σ(n)：只要找到它们关于质数幂次的表达式和积性性质，就能在线性筛中一并求出。

一个通用的线性筛框架可以同时求出质数、欧拉函数、莫比乌斯函数、最小质因数等，代码结构高度相似，只是递推公式不同。这体现了算法设计的模块化和复用思想。

最后，回顾整个“Relatives”问题的解决过程，从理解题意到选择策略，从推导数学公式到实现精妙递推，再到调试优化和思考扩展，这正是一个典型算法问题从分析到解决的完整路径。我个人的体会是，数论问题往往代码不长，但对思维严密性要求极高。理解每一个等号为什么成立，每一个if条件背后的数学含义，比死记硬背模板重要得多。下次当你遇到需要计算互质个数的问题时，希望你能立刻想起“素数筛+欧拉函数”这个黄金组合，并自信地写出高效的代码。