线性筛（欧拉筛）求欧拉函数

引言：为什么要用线性筛？

在之前的学习中，我们掌握了求单个数欧拉函数 $\varphi(n)$ 的方法，其时间复杂度是 $O(\sqrt{n})$。

但在算法竞赛中，我们经常面临这样的需求：求 $1$ 到 $N$（例如 $10^7$）之间所有整数的欧拉函数值。

如果我们对每个数都单独计算，总复杂度将高达 $O(N\sqrt{N})$。对于 $N=10^7$，这意味着 $10^{10}$ 次运算，绝对会 TLE（超时）。

这时候，我们需要引入线性筛（欧拉筛）。它不仅能以 $O(N)$ 的线性时间复杂度筛出素数，还能利用积性函数的性质，顺手把欧拉函数表也递推计算出来。这就是 $O(N)$ 的魔法。

1 前置知识：积性函数

理解线性筛求 $\varphi$ 的前提，是理解欧拉函数的积性。

定义：如果不相等的两个数 $a, b$ 互质（即 $\gcd(a, b) = 1$），那么：

这个性质非常关键，它是我们在筛法中处理 i % p != 0 情况的理论基础。

2 核心逻辑：三种情况的递推

线性筛的核心机制是：确保每个合数只被它的“最小质因子”筛掉。 在筛选过程中，我们从小到大枚举数值 $i$，并枚举已有的素数 $p$。我们要计算的是 $\varphi(i \times p)$。

根据 $i$ 和 $p$ 的关系，分为三种情况：

情况 1：$i$ 是质数

这是最基础的情况。根据欧拉函数的定义，质数 $p$ 只有 $1$ 和它本身两个因子，与小于它的 $p-1$ 个数都互质。

(在代码中，这通常在判断出质数时直接赋值)

情况 2：$i \bmod p \neq 0$ （$i$ 和 $p$ 互质）

此时，$p$ 是质数，且 $p$ 不是 $i$ 的因子。显然 $\gcd(i, p) = 1$。 利用欧拉函数的积性：

情况 3：$i \bmod p = 0$ （$i$ 和 $p$ 不互质，核心难点！）

当 $i \bmod p = 0$ 时，说明 $p$ 已经是 $i$ 的因子了（实际上是最小质因子）。 这意味着：$i \times p$ 的质因子种类，与 $i$ 的质因子种类完全相同。 $p$ 并没有带来新的质因子，只是让原有的质因子 $p$ 的指数加 1 了。

让我们看欧拉函数的通项公式：

• 对于 $i$：
  $$\varphi(i) = i \times \prod (1 - \frac{1}{p_k})$$
• 对于 $i \times p$：
  $$\begin{aligned} \varphi(i \times p) &= (i \times p) \times \prod (1 - \frac{1}{p_k}) \\ &= p \times \left[ i \times \prod (1 - \frac{1}{p_k}) \right] \\ &= p \times \varphi(i) \end{aligned}$$

结论：当 $i \bmod p = 0$ 时，递推公式为：

我们通过两个具体的例子来剖析 i % p == 0 的情况。

例子 1：普通合数的情况

假设当前枚举到：

• $i = 6$
• $p = 2$ （$p$ 是 $6$ 的最小质因子，满足 6 % 2 == 0）

我们要计算的目标是 $\varphi(12)$ （即 $\varphi(6 \times 2)$）。

1. 先看 $\varphi(i)$ 即 $\varphi(6)$： $6$ 的质因子是 $\{2, 3\}$。 根据通项公式：

2. 再看 $\varphi(i \times p)$ 即 $\varphi(12)$： $12$ 的质因子依然是 $\{2, 3\}$。（虽然多乘了一个 $2$，但并没有引入新的质数，比如 $5$ 或 $7$）。 根据通项公式：

3. 对比发现： 你会发现 $\varphi(12)$ 和 $\varphi(6)$ 的公式中，后面括号里的那一长串完全一样。 唯一的区别就是前面的系数从 $6$ 变成了 $12$（扩大了 $2$ 倍，即 $p$ 倍）。

所以：

例子 2：纯素数幂次的情况

假设当前枚举到：

• $i = 4$ ($2^2$)
• $p = 2$ （满足 4 % 2 == 0）

我们要计算的目标是 $\varphi(8)$ （即 $\varphi(4 \times 2)$）。

1. 先看 $\varphi(4)$： $4$ 的质因子只有 $\{2\}$。

2. 再看 $\varphi(8)$： $8$ ($2^3$) 的质因子依然只有 $\{2\}$。并没有因为多乘了个 $2$ 就变成了别的。

3. 结论： 同样，后面括号里的部分完全没变。只有前面的系数乘了 $p$。

反面教材：如果误用了“积性函数”公式会怎样？

有些同学会习惯性地认为 $\varphi(A \times B) = \varphi(A) \times \varphi(B)$ 永远成立。 这是错误的！这只在 $\gcd(A, B)=1$ 时成立。

如果在 i % p == 0 时（比如 $i=6, p=2$）强行套用积性公式：

• 错误计算：$\varphi(6 \times 2) \stackrel{?}{=} \varphi(6) \times \varphi(2) = 2 \times 1 = 2$ ❌
• 正确值：$\varphi(12) = 4$ ✅

为什么错了？ 因为 $6$ 和 $2$ 不互质。它们共享了因子 $2$。 当我们计算 $\varphi(6)$ 时，已经乘过一次 $(1 - \frac{1}{2})$ 了。 当我们计算 $\varphi(2)$ 时，又乘了一次 $(1 - \frac{1}{2})$。 如果直接相乘，会导致 $(1 - \frac{1}{2})$ 被乘了两次，导致结果偏小。

而线性筛的正确公式 $\varphi(i \times p) = \varphi(i) \times p$ 刚好避免了这个问题，因为它只调整了前面的倍数 $n$，没有动后面的 $\prod(1 - 1/p)$。

3 C++ 代码模板

这是标准的模板代码，包含了详细的注释，建议理解并背诵。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

        #include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1000005; 

int phi[MAXN];          // 存储欧拉函数值
vector<int> primes;     // 存储质数
bool st[MAXN];          // st[i] = true 代表 i 是合数（被筛掉了）

void get_phi_linear(int n) {
    // 1. 初始化边界
    phi[1] = 1;
    
    // 2. 线性筛过程
    for (int i = 2; i <= n; ++i) {
        // --- 情况 1: i 是质数 ---
        if (!st[i]) {
            primes.push_back(i);
            phi[i] = i - 1; // 质数的欧拉函数是 p-1
        }
        
        // 枚举已有的质数 p，作为最小质因子去筛合数 (i * p)
        for (int p : primes) {
            // 越界检查
            if (i * p > n) break; 
            
            // 标记合数
            st[i * p] = true; 
            
            if (i % p == 0) {
                // --- 情况 3: p 是 i 的因子 (Break条件) ---
                // i * p 的最小质因子是 p，且 p 已经包含在 i 的质因子分解中了
                // 此时质因子种类不变，仅数值扩大 p 倍
                phi[i * p] = phi[i] * p;
                
                // 【关键 Break】
                // 保证每个合数只被它的最小质因子筛掉。
                break;
            } else {
                // --- 情况 2: p 和 i 互质 ---
                // 利用欧拉函数的积性
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
}

int main() {
    get_phi_linear(100);
    
    cout << "phi(10) = " << phi[10] << endl; // 4
    cout << "phi(12) = " << phi[12] << endl; // 4
    cout << "phi(13) = " << phi[13] << endl; // 12
    return 0;
}

    

4 记忆口诀

在考场上，为了快速准确地写出代码，可以记忆这三个分支：

1. 遇见质数：$\varphi(i) = i - 1$
2. 互质乘积（i % p != 0）：积性生效，$\varphi(ip) = \varphi(i) \times (p - 1)$
3. 包含因子（i % p == 0）：直接乘倍数，$\varphi(ip) = \varphi(i) \times p$

5 复杂度分析

• 时间复杂度：$O(N)$。 得益于 if (i % p == 0) break; 这一行，每个合数 $x$ 只会被它的最小质因子筛除一次。这意味着循环体内的操作次数严格等于 $N$ 的量级。
• 空间复杂度：$O(N)$。 需要 phi 数组和 st 数组（或 primes 数组）来存储数据。

总结

线性筛不仅仅是用来找质数的，它是一把处理积性函数的“瑞士军刀”。

只要掌握了这个模板，你就可以通过修改几行递推公式，轻松求出：

• 莫比乌斯函数 $\mu(n)$
• 约数个数 $d(n)$
• 约数和 $\sigma(n)$

它们的逻辑完全一致：在 i % p == 0 和 i % p != 0 时分别套用对应的数学性质。掌握了它，你就拿到了通往高级数论题目的入场券！

练习题目

• luogu-P2568 GCD tags: [数论,欧拉函数]