CC++ & Algorithm

线性筛求欧拉函数

极难2
语言版本：通用
概述：利用线性筛（欧拉筛）可以在O(n)时间内求出从1到n所有整数的欧拉函数值，非常适合批量计算。

用线性筛一口气算出1到n所有数的欧拉函数值

你有没有遇到过这样的题目：“请计算从1到1000中，有多少个数与1000互质？”或者“密码学中需要生成很多个欧拉函数值，怎样批量算得快？”如果只用之前学的质因数分解法，一个一个算会非常慢——每个数最多要试除掉√n次，加起来就是O(n√n)，当n=10^6时，运算次数高达10^9，电脑也得算半天。

其实，我们可以用线性筛（欧拉筛） 在O(n) 时间就把1~n所有整数的φ值全部算出来。这就像在超市里一次性买齐一周的菜，比每天跑一趟快得多。线性筛原本是快速找质数的，但它还能“顺手”把欧拉函数也算完。今天我们就来学会这个神奇的方法。

回顾：欧拉函数是什么？

对于正整数n，欧拉函数φ(n)表示小于等于n且与n互质的正整数的个数。比如φ(6)=2，因为1和5与6互质（2、3、4都与6有公因数）。

之前我们学过用质因数分解求单个φ(n)：
若n = p₁^a₁ * p₂^a₂ * … * pₖ^aₖ，则
φ(n) = n * (1-1/p₁) * (1-1/p₂) * … * (1-1/pₖ)。
这个方法每次都要分解n，很耗时。

线性筛求欧拉函数的思路

线性筛的原理是：每个合数只被它的最小质因子筛掉一次。在筛的过程中，我们已知当前数i的φ值，并且可以推出所有形如i×p（p是质数）的数的φ值。这样一传十、十传百，所有数的φ值就都出来了。

我们需要三个数组：

  • is_prime：标记每个数是不是质数（或者是否已被筛掉）
  • primes：存放已找到的所有质数
  • phi：存放每个数的φ值

算法流程非常像玩“筛子游戏”：从2开始，逐个数字往前走；每遇到一个没被筛掉的数，它就是质数；然后拿它去筛后面的合数；筛的时候根据条件算出合数的φ值。

两种递推公式，一次学会

在筛的过程中，我们假定已经知道φ(i)，现在要算φ(i×p)（p是质数）。有两种情况：

情况一：p能整除i（即i % p == 0）
此时p是i的质因子，而且因为primes从小到大枚举，p就是i的最小质因子。那么φ(i×p) = φ(i) × p。
为什么不是乘(p-1)？因为i和p不互质，不能直接用积性函数。一个直观理解：i×p比i多了一个p因子，但i里已经有p了，所以相当于把i中p的指数加1。根据质数幂的欧拉公式，φ(p^(k+1)) = p^(k+1) - p^k = p × (p^k - p^(k-1)) = p × φ(p^k)。而φ(i)中包含φ(p^k)的乘积，所以整体乘p即可。

情况二：p不能整除i（即i % p != 0）
此时p和i互质，那么欧拉函数是积性函数：φ(i×p) = φ(i) × φ(p) = φ(i) × (p-1)。

用生活例子来理解这两个公式

假设我们有一堆苹果，i表示苹果堆里不同品种的数量（互质关系），p代表一种新的水果品种。

  • 如果新水果p和苹果堆里的品种不重复（p不是i的质因子），那么混合后互质的情况就相当于：原来苹果堆里的互质数，和p的互质数（p-1）可以自由组合，所以总数是φ(i)×(p-1)。
  • 如果p已经在苹果堆里（p是i的质因子），那就相当于给这个品种加了1倍，那么互质数的数量只会按比例增加p倍，而不是(p-1)倍。因为原来和这个品种互质的数，现在依然和它互质（只不过基数变了）。

线性筛求欧拉函数的完整步骤

  1. 初始化phi[1] = 1（1与任何数互质，φ(1)=1）。
  2. 从i=2到n循环：
    • 如果is_prime[i]为真，说明i是质数，将i加入primes，并设置phi[i] = i - 1。
    • 遍历primes中的每个质数p：
      • 如果i×p > n，退出循环。
      • 将i×p标记为合数。
      • 如果i % p == 0：phi[i×p] = phi[i] * p，然后break（这是关键！）。
      • 否则：phi[i×p] = phi[i] * (p-1)，继续循环。

为什么当i % p == 0时要break？
因为如果继续用更大的质数q（q>p）去筛i×q，那么i×q的最小质因子其实是p（因为p整除i），而不是q。如果不break，这个合数会被后面的q再次筛到，造成重复。break保证了每个合数只被它的最小质因子筛一次，算法才是线性的。

编程实现：C++代码（带详细注释）

#include <iostream>
#include <vector>
using namespace std;

// 线性筛求 1 到 n 所有数的欧拉函数值，结果保存在phi数组中
void linear_sieve_phi(int n, vector<int>& phi) {
    vector<bool> is_prime(n + 1, true); // 标记是否是质数，初始全为true
    vector<int> primes;                 // 存储找到的质数
    phi[1] = 1;                         // 1的欧拉函数值为1

    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {              // 如果i没有被筛掉，说明它是质数
            primes.push_back(i);
            phi[i] = i - 1;             // 质数的欧拉函数值 = i-1
        }
        // 用当前所有质数去筛掉合数
        for (int p : primes) {
            long long x = 1LL * i * p;   // 防止i*p溢出，用long long临时存
            if (x > n) break;
            is_prime[x] = false;        // 标记为合数
            if (i % p == 0) {           // p是i的最小质因子
                phi[x] = phi[i] * p;    // 公式1
                break;                  // 核心：每个合数只被最小质因子筛一次
            } else {
                phi[x] = phi[i] * (p - 1); // 公式2（互质情况）
            }
        }
    }
}

int main() {
    int n;
    cout << "请输入一个正整数 n: ";
    cin >> n;

    vector<int> phi(n + 1);            // 欧拉函数数组，索引从0到n
    linear_sieve_phi(n, phi);

    // 显示前20个数的欧拉函数值作为示例
    int show = min(n, 20);
    cout << "前 " << show << " 个数的欧拉函数值：" << endl;
    for (int i = 1; i <= show; i++) {
        cout << "φ(" << i << ") = " << phi[i] << endl;
    }
    return 0;
}

代码小贴士：C++中vector<bool>是特化版本，每个元素只占1位，非常省内存。1LL * i * p是为了防止乘法溢出（当i和p都很大时）。

Python代码实现（同样详细注释）

def linear_sieve_phi(n):
    # 欧拉函数数组，索引从0到n
    phi = [0] * (n + 1)
    # 标记是否是质数，初始全为True
    is_prime = [True] * (n + 1)
    # 存储质数
    primes = []
    phi[1] = 1  # 1的欧拉函数

    for i in range(2, n + 1):
        if is_prime[i]:          # i是质数
            primes.append(i)
            phi[i] = i - 1
        # 用质数去筛合数
        for p in primes:
            x = i * p
            if x > n:
                break
            is_prime[x] = False
            if i % p == 0:        # p是i的最小质因子
                phi[x] = phi[i] * p
                break
            else:
                phi[x] = phi[i] * (p - 1)
    return phi

# 主程序
n = int(input("请输入 n: "))
phi = linear_sieve_phi(n)
show = min(n, 20)
print(f"前 {show} 个数的欧拉函数值：")
for i in range(1, show + 1):
    print(f"φ({i}) = {phi[i]}")

温馨提示：Python的循环比C++慢，但n=10^6时仍能在1秒内完成。如果n=10^7，可能需要几秒钟，作为学习体验完全足够。

常见错误（新手必看）

  1. 忘记初始化phi[1]：欧拉函数φ(1)=1，如果不设置，后面递推可能会用垃圾值。
  2. 当i % p == 0时忘记break：会导致同一个合数被多次筛掉，破坏线性复杂度，甚至算错φ值（因为后面的质数q不是最小质因子，用公式2会算出错误结果）。
  3. 把phi[i]初值设成0：对于质数i，phi[i] = i-1必须正确赋值，否则后面递推的基数错了。
  4. 数组越界：要保证phi和is_prime的长度是n+1，因为下标从1到n。循环中注意i * p可能超过n，需要提前break。
  5. 混淆phi[i] * p和phi[i] * (p-1)：区分两种情况的标志是i % p是否为0，一定要想清楚。

运行示例：验证正确性

我们手动算几个，再和程序输出对比：

  • φ(1) = 1
  • φ(2) = 1（质数）
  • φ(3) = 2
  • φ(4) = 2（4=2²，互质数：1,3）
  • φ(5) = 4
  • φ(6) = 2（1,5与6互质）
  • φ(7) = 6
  • φ(8) = 4（1,3,5,7）
  • φ(9) = 6（1,2,4,5,7,8）
  • φ(10) = 4（1,3,7,9）

如果程序输出以上结果，说明算法正确。

为什么线性筛这么快？

假设n=10^6，用线性筛只需要大约1毫秒（C++），而用单个质因数分解需要10^9次运算，差了一百万倍！当你要处理密码学、数论题目中的大量欧拉函数时，线性筛是必须掌握的工具。

总结

  • 线性筛利用最小质因子唯一性，在O(n)内算出所有数的欧拉函数。
  • 掌握两种递推公式：i%p==0时乘p，否则乘(p-1)。
  • 代码中break是灵魂，确保每个合数只处理一次。
  • 适用于n≤10^7的场景，比逐个分解快几千倍。

接下来学什么？

欧拉函数是欧拉定理的基石。下一讲我们将学习欧拉定理：如果a和n互质，那么a^φ(n) ≡ 1 (mod n)。它把模幂运算和欧拉函数联系起来，是RSA加密算法的核心哦！准备好迎接下一个挑战吧！

例题精讲

1单选题

在线性筛求欧拉函数时，若当前数 i 与质数 p 满足 i % p == 0，则 φ(i * p) 等于多少？

Aφ(i) * (p - 1)
Bφ(i) * p
Cφ(i) * (p + 1)
Dφ(i) * (p - 1) / p
2单选题

线性筛求欧拉函数的时间复杂度是？

AO(n log n)
BO(n)
CO(n log log n)
DO(n√n)
3判断题

在线性筛求欧拉函数时，对于每个质数p，φ(p)=p-1。

4填空题
以下代码用线性筛求1到n的欧拉函数。请填空：
int phi[N], prime[N];
bool is_composite[N];
void get_phi(int n) {
    int cnt = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!is_composite[i]) {
            prime[++cnt] = i;
            phi[i] = ___;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
            is_composite[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * ___;
                break;
            } else {
                phi[i * prime[j]] = phi[i] * ___;
            }
        }
    }
}
5填空题
在线性筛求欧拉函数的代码中，最关键的一步是当 i % prime[j] == 0 时使用 break 语句，其目的是保证每个合数只被其___筛掉。