筛法

1. 什么是筛法

筛法（Sieve Method）是一类在计算理论，尤其是数论中，用于高效找出一定范围内所有满足特定性质的数的算法。其核心思想类似于“筛选”：从一个包含所有可能候选数的集合开始，通过一系列系统性的排除操作，将不满足性质的数（通常是合数）剔除，最终剩下的就是我们所需要的数（通常是质数）。

筛法最经典和最基础的应用是寻找范围内的所有质数，即质数筛。我们将从最古老的埃拉托斯特尼筛法（Sieve of Eratosthenes）讲起，并逐步深入到更高效的线性筛法（Linear Sieve），最后探讨筛法思想的扩展应用。

2. 埃拉托斯特尼筛法（Sieve of Eratosthenes）

埃拉托斯特尼筛法，简称埃氏筛，由古希腊数学家埃拉托斯特尼在公元前3世纪提出，是第一个也是最著名的质数筛选算法。

2.1 核心思想

埃氏筛的原理非常直观：

1. 创建一个布尔数组 $is\_p$，初始时将所有大于等于 $2$ 的数都标记为质数。
2. 从最小的质数 $2$ 开始，将所有 $2$ 的倍数（$4, 6, 8, \dots$）标记为合数。
3. 找到下一个未被标记的数，这个数一定是质数（因为如果它是合数，那么它一定有一个比它更小的质因子，而这个质因子在之前的步骤中就应该已经把它标记为合数了）。这个数是 $3$。
4. 将所有 $3$ 的倍数（$6, 9, 12, \dots$）标记为合数。
5. 重复这个过程，找到下一个未被标记的质数 $p$，然后将所有 $p$ 的倍数标记为合数。
6. 这个过程持续到我们检查的质数 $p$ 的平方 $p^2$ 大于要筛选的范围上限 $N$ 为止。因为如果一个合数 $n$ 的最小质因子大于 $\sqrt{N}$，那么 $n$ 至少是两个大于 $\sqrt{N}$ 的数的乘积，其结果必然大于 $N$，这超出了我们的范围。

2.2 过程

假设我们需要找出 $1$ 到 $20$ 之间的所有质数。

1. 初始状态，我们认为 $2$ 到 $20$ 都是质数。 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2. 找到第一个质数 $2$，划掉它的所有倍数（$4, 6, 8, \dots, 20$）。 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 剩下的可能是质数的数：2 3 5 7 9 11 13 15 17 19

3. 找到下一个质数 $3$，划掉它的所有倍数（$6, 9, 12, 15, 18$）。其中一些已经被划掉了。 2 3 5 7 9 11 13 15 17 19 剩下的可能是质数的数：2 3 5 7 11 13 17 19

4. 找到下一个质数 $5$。它的平方是 $25$，已经大于 $20$，所以我们停止筛选。

最终，所有未被划掉的数就是 $20$ 以内的质数：$2, 3, 5, 7, 11, 13, 17, 19$。

2.3 代码实现

基础版本

题意概括: 找出并打印 $1$ 到 $N$ 之间的所有质数。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1000005;
bool isp[N]; // is prime? isp[i]为true代表i是质数

void sieve(int n) {
    memset(isp, 1, sizeof(isp)); // 初始化，假设所有数都是质数
    isp[0] = isp[1] = 0; // 0和1不是质数

    for (int i = 2; i <= n; ++i) {
        if (isp[i]) { // 如果i是质数
            // 将i的倍数标记为合数
            // j可以从2*i开始，也可以从i*i开始，后者是优化
            for (int j = 2 * i; j <= n; j += i) {
                isp[j] = 0;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    sieve(n);
    for (int i = 2; i <= n; ++i) {
        if (isp[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

• 代码解释：isp 数组用于标记。sieve 函数中，外层循环遍历 $2$ 到 $n$ 的所有数。如果发现 isp[i] 仍然为 true，说明 $i$ 是一个质数，因为它没有被任何比它小的质数筛掉。然后，内层循环就将 $i$ 的所有倍数标记为合数。
• 时间复杂度分析：外层循环遍历每个数，内层循环对每个质数 $p$ 会执行 $N/p$ 次操作。所以总的操作次数近似为 $\sum_{p \le N, p \text{ is prime}} \frac{N}{p}$。根据梅滕斯第二定理，质数倒数之和近似于 $\ln(\ln N)$。所以，埃氏筛的时间复杂度为 $O(N \log \log N)$。这是一个非常接近线性的高效复杂度。
• 空间复杂度分析：我们需要一个大小为 $N+1$ 的布尔数组来记录每个数是否为质数，所以空间复杂度为 $O(N)$。

优化版本

我们可以对基础版本做一些优化。

1. 内层循环起点：对于一个质数 $p$，它的倍数 $2p, 3p, \dots, (p-1)p$ 其实在之前的步骤中已经被 $2, 3, \dots$ 等更小的质数筛过了。例如，筛 $3$ 的倍数时，$2 \times 3 = 6$ 已经在筛 $2$ 的时候被处理。因此，我们可以让内层循环直接从 $p \times p$ 开始。这是因为任何一个合数 $n = a \times b$（不妨设 $a \le b$），它必然有一个小于等于 $\sqrt{n}$ 的质因子。当我们的筛子进行到 $a$ 时，$n$ 就已经被筛掉了。所以对于质数 $p$，小于 $p^2$ 的 $p$ 的倍数，都已经被更小的质数处理过。

2. 外层循环终点：同理，外层循环的 $i$ 只需要遍历到 $\sqrt{N}$ 即可。因为如果一个数 $j > \sqrt{N}$ 是合数，它的最小质因子一定小于等于 $\sqrt{j}$。如果我们只对小于等于 $\sqrt{N}$ 的质数进行筛选，那么所有 $N$ 以内的合数都会被它们小于等于 $\sqrt{N}$ 的质因子筛掉。

题意概括: 优化地找出并打印 $1$ 到 $N$ 之间的所有质数。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1000005;
bool isp[N];

void sieve(int n) {
    memset(isp, 1, sizeof(isp));
    isp[0] = isp[1] = 0;

    for (int i = 2; i * i <= n; ++i) { // 优化1：外层循环到sqrt(n)
        if (isp[i]) {
            // 优化2：内层循环从i*i开始
            for (ll j = (ll)i * i; j <= n; j += i) {
                isp[j] = 0;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    sieve(n);
    for (int i = 2; i <= n; ++i) {
        if (isp[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

• 代码解释：注意 j 的类型为 ll (long long)，防止 i * i 溢出。这个优化后的版本在实践中效率更高，但其时间复杂度的理论上界仍然是 $O(N \log \log N)$。

2.4 埃氏筛的局限性

埃氏筛虽然高效，但它存在一个问题：一个合数可能会被它的多个质因子重复筛选。

例如，数字 $12$：

• 在筛质数 $2$ 时， $12 = 2 \times 6$ 被标记为合数。
• 在筛质数 $3$ 时， $12 = 3 \times 4$ 又被标记了一次。

这种重复操作虽然不影响结果的正确性，但却是时间上的浪费。如果我们能让每个合数都只被筛选一次，能否做到严格的 $O(N)$ 复杂度呢？答案是肯定的，这就是线性筛法。

3. 线性筛法（Linear Sieve）

线性筛法，也称为欧拉筛（Euler's Sieve），是一种能在严格线性时间内，即 $O(N)$ 时间内找出所有质数的算法。它的核心思想是确保每个合数都只被其最小质因子（Smallest Prime Factor, SPF）筛选一次。

3.1 核心思想与原理

为了实现“只被最小质因子筛选”，线性筛在遍历每个数 $i$ 的时候，不仅仅是标记 $i$ 的倍数，而是利用已经找到的质数来构造合数。

具体步骤如下：

1. 我们需要一个数组 $p$ 来存储已经找到的质数，一个计数器 $cnt$ 记录质数个数。同样，需要一个布尔数组 $isp$ 来标记。
2. 我们从 $2$ 开始遍历到 $N$。
3. 对于当前遍历到的数 $i$： a. 如果 isp[i] 仍然为 true（或者在某些实现中用 $0$ 表示未被标记），说明 $i$ 是一个质数。我们将它存入质数数组 $p$ 中，即 p[cnt++] = i;。 b. 关键步骤：不论 $i$ 是质数还是合数，我们都要用它去与已经找到的质数 $p[j]$ 相乘，来筛选掉新的合数 i * p[j]。 c. 我们遍历质数数组 $p$，对于每个质数 p[j]，将 i * p[j] 标记为合数。 d. 终止条件：这个遍历质数数组的过程需要一个终止条件，以确保“只被最小质因子筛选”。这个条件是：如果 $i$ 是 $p[j]$ 的倍数，即 i % p[j] == 0，则立刻停止内层循环。

3.2 原理证明：为何 i % p[j] == 0 时要停止？

这是线性筛的精髓所在。让我们来分析一下。

我们正在用数 $i$ 和质数 $p[j]$ 来筛选合数 $i \times p[j]$。我们希望这个合数是被它的最小质因子筛掉的。

• Case 1: i % p[j] != 0 在这种情况下，$p[j]$ 是比 $i$ 的所有质因子都要小的。因为我们是按顺序遍历质数数组 $p$ 的，所以 $p[j]$ 是我们当前能用的最小的质数之一。由于 $i$ 不能被 $p[j]$ 整除，所以 $i$ 的最小质因子必然大于 $p[j]$。因此，合数 $i \times p[j]$ 的最小质因子就是 $p[j]$。这符合我们的要求：合数 $i \times p[j]$ 被其最小质因子 $p[j]$ 筛掉。

• Case 2: i % p[j] == 0 在这种情况下，$i$ 本身就是 $p[j]$ 的倍数。这意味着 $p[j]$ 是 $i$ 的一个质因子，而且由于我们是按从小到大的顺序遍历质数 $p$ 的，所以 $p[j]$ 一定是 $i$ 的最小质因子。

  此时，我们筛掉了合数 $i \times p[j]$。它的最小质因子是 $p[j]$，这没有问题。

  但是，如果我们继续内层循环，用下一个质数 $p[j+1]$ 去和 $i$ 相乘，会得到合数 $i \times p[j+1]$。让我们来分析这个新合数。

  因为 $i = k \times p[j]$（$k$ 是某个整数），所以 $i \times p[j+1] = k \times p[j] \times p[j+1]$。

  这个新合数 $i \times p[j+1]$ 的最小质因子是什么？由于 $p[j] < p[j+1]$，所以它的最小质因子是 $p[j]$，而不是 $p[j+1]$。

  这意味着，如果我们继续循环，合数 $i \times p[j+1]$ 将会被 $p[j+1]$ 筛掉。但我们希望它被它的最小质因子 $p[j]$ 筛掉。这个数应该在什么时候被筛掉呢？它应该在遍历到数 $i' = k \times p[j+1]$ 时，与质数 $p[j]$ 相乘时被筛掉，即 $i' \times p[j] = (k \times p[j+1]) \times p[j]$。

  所以，为了保证每个合数只被其最小质因子筛掉，一旦我们发现 i % p[j] == 0，就必须 break。因为后续用 $i$ 和更大的质数 $p[j+1], p[j+2], \dots$ 构造出的合数，它们的最小质因子都会是 $p[j]$，而不是 $p[j+1], p[j+2], \dots$。这些合数应该留给后面某个 $i'$（其最小质因子大于 $p[j]$）去处理。

通过这个 break 条件，我们完美地保证了每个合数 $N$ 都是以 $N = i \times p$ 的形式被筛掉的，其中 $p$ 是 $N$ 的最小质因子。

3.3 代码实现

题意概括: 使用线性筛法，找出并打印 $1$ 到 $N$ 之间的所有质数，并记录每个数的最小质因子。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 10000005;
bool isp[N]; // is prime? 0代表质数，1代表合数
int p[N / 10]; // 存放质数
int spf[N]; // smallest prime factor
int cnt; // 质数计数

void sieve(int n) {
    memset(isp, 0, sizeof(isp));
    isp[0] = isp[1] = 1;

    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) { // i是质数
            p[cnt++] = i;
            spf[i] = i; // 质数的最小质因子是它自己
        }
        // 遍历已找到的质数来筛合数
        // i * p[j] 是要筛掉的合数
        for (int j = 0; j < cnt && (ll)i * p[j] <= n; ++j) {
            int np = p[j]; // 当前质数
            isp[i * np] = 1; // 标记为合数
            spf[i * np] = np; // i*np的最小质因子是np

            if (i % np == 0) { // 关键：i的最小质因子是np
                break; // 保证每个合数只被最小质因子筛一次
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    sieve(n);
    for (int i = 0; i < cnt; ++i) {
        cout << p[i] << " ";
    }
    cout << endl;
    return 0;
}

• 代码解释：
  • isp 数组的含义与埃氏筛相反，0 代表未被筛（质数），1 代表已被筛（合数）。
  • p 数组用来存储找到的质数，cnt 是当前质数的数量。
  • spf 数组（Smallest Prime Factor）记录每个数的最小质因子，这是线性筛的一个非常有用的副产品。
  • 外层循环遍历 $2$ 到 $n$。如果 $i$ 是质数，就加入 $p$ 数组。
  • 内层循环用 $i$ 和已知的质数 $p[j]$ 来构造合数。循环有两个退出条件：一是构造的合数 i * p[j] 超出了范围 $n$；二就是 i % p[j] == 0。
• 时间复杂度分析：外层循环是 $O(N)$。关键是内层循环。由于每个合数 $k$ 都只会被它的最小质因子 $p_{min}$ 在 $i = k / p_{min}$ 时筛一次，所以内层循环的总执行次数等于 $N$ 以内的合数个数。因此，总的时间复杂度是 $O(N)$。
• 空间复杂度分析：需要 isp, p, spf 三个数组。isp 和 spf 是 $O(N)$，$p$ 的大小约为 $N / \ln N$（根据质数定理），所以总空间复杂度为 $O(N)$。

4. 筛法思想的扩展应用

线性筛的强大之处不仅在于求质数，它的核心思想——“每个数只被特定因子处理一次”——可以被推广用来求解很多数论函数的前缀信息，这类函数被称为积性函数。

4.1 积性函数简介

一个数论函数 $f(n)$，如果对于任意两个互质的正整数 $a$ 和 $b$（即 $\gcd(a, b) = 1$），都有 $f(ab) = f(a)f(b)$，那么称 $f(n)$ 为积性函数。

如果对于任意两个正整数 $a, b$（不要求互质），都有 $f(ab) = f(a)f(b)$，则称其为完全积性函数。

常见的积性函数：

• 欧拉函数 $\varphi(n)$：小于等于 $n$ 的正整数中与 $n$ 互质的数的数目。
• 莫比乌斯函数 $\mu(n)$：
  • $\mu(1) = 1$
  • 若 $n$ 含有平方因子（即能被某个 $p^2$ 整除），$\mu(n) = 0$。
  • 若 $n$ 是 $k$ 个不同质数的乘积，$\mu(n) = (-1)^k$。
• 约数个数函数 $d(n)$ 或 $\tau(n)$：$n$ 的正约数的个数。
• 约数和函数 $\sigma(n)$：$n$ 的正约数的和。

4.2 线性筛求欧拉函数 $\varphi(n)$

欧拉函数的计算公式为： 若 $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$ 是 $n$ 的标准分解式，则

$$\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right) = n \frac{p_1-1}{p_1} \frac{p_2-1}{p_2} \dots \frac{p_k-1}{p_k} $$

在线性筛的框架内，我们考虑如何计算 $\varphi(i \times p_j)$。设 $p_j$ 是当前质数。

1. 当 $i$ 是质数时： 对于一个质数 $p$，$\varphi(p) = p - 1$。这可以在筛到质数时直接计算。

2. 当 $i \times p_j$ 是合数时，我们利用积性函数的性质。设 $p_j$ 是 $i \times p_j$ 的最小质因子。

   • Case 1: i % p_j != 0 此时 $i$ 和 $p_j$ 互质。根据积性函数的定义，$\varphi(i \times p_j) = \varphi(i) \times \varphi(p_j)$。 因为 $p_j$ 是质数，$\varphi(p_j) = p_j - 1$。 所以，$\varphi(i \times p_j) = \varphi(i) \times (p_j - 1)$。

   • Case 2: i % p_j == 0 此时 $i$ 和 $p_j$ 不互质，$p_j$ 是 $i$ 的最小质因子。 这意味着 $i$ 和 $i \times p_j$ 含有完全相同的质因子集合。 设 $i = m \times p_j^k$，其中 $\gcd(m, p_j)=1$。 则 $i \times p_j = m \times p_j^{k+1}$。 根据 $\varphi(n)$ 的计算公式： $\varphi(i) = i \prod_{p|i} (1-\frac{1}{p}) = (m \times p_j^k) \prod_{p|i} (1-\frac{1}{p})$ $\varphi(i \times p_j) = (i \times p_j) \prod_{p|i \times p_j} (1-\frac{1}{p})$ 因为 $i$ 和 $i \times p_j$ 的质因子集合相同，所以它们的 $\prod (1-\frac{1}{p})$ 部分是完全一样的。 $\frac{\varphi(i \times p_j)}{\varphi(i)} = \frac{i \times p_j}{i} = p_j$ 所以，$\varphi(i \times p_j) = \varphi(i) \times p_j$。

总结一下递推关系：

• 如果 $p$ 是质数，$\varphi(p) = p-1$。
• 如果 $i \% p_j \neq 0$，$\varphi(i \cdot p_j) = \varphi(i) \cdot \varphi(p_j) = \varphi(i) \cdot (p_j - 1)$。
• 如果 $i \% p_j = 0$，$\varphi(i \cdot p_j) = \varphi(i) \cdot p_j$。

代码实现

题意概括: 使用线性筛，计算并存储 $1$ 到 $N$ 所有数的欧拉函数值。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1000005;
bool isp[N];
int p[N / 10];
int phi[N];
int cnt;

void sieve(int n) {
    memset(isp, 0, sizeof(isp));
    isp[0] = isp[1] = 1;
    phi[1] = 1;

    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) { // i是质数
            p[cnt++] = i;
            phi[i] = i - 1; // 质数p的phi(p) = p-1
        }
        for (int j = 0; j < cnt && (ll)i * p[j] <= n; ++j) {
            int np = p[j];
            isp[i * np] = 1;
            if (i % np == 0) { // i的最小质因子是np
                phi[i * np] = phi[i] * np;
                break;
            } else { // i和np互质
                phi[i * np] = phi[i] * (np - 1);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    sieve(n);
    // 打印前20个欧拉函数值作为示例
    for (int i = 1; i <= min(n, 20); ++i) {
        cout << "phi(" << i << ") = " << phi[i] << endl;
    }
    return 0;
}

• 复杂度分析：与标准线性筛完全相同，时间复杂度和空间复杂度均为 $O(N)$。

4.3 线性筛求莫比乌斯函数 $\mu(n)$

同样，我们可以在线性筛框架内递推计算 $\mu(n)$。

1. 当 $i$ 是质数时： 根据定义，质数 $p$ 是 1 个不同质数的乘积，所以 $\mu(p) = (-1)^1 = -1$。

2. 当 $i \times p_j$ 是合数时：

   • Case 1: i % p_j != 0 此时 $i$ 和 $p_j$ 互质。根据积性函数定义，$\mu(i \times p_j) = \mu(i) \times \mu(p_j)$。 因为 $\mu(p_j) = -1$，所以 $\mu(i \times p_j) = -\mu(i)$。

   • Case 2: i % p_j == 0 此时 $i$ 含有质因子 $p_j$。那么 $i \times p_j$ 必然含有平方因子 $p_j^2$。 根据定义，任何含有平方因子的数，其莫比乌斯函数值为 $0$。 所以，$\mu(i \times p_j) = 0$。

总结一下递推关系：

• $\mu(1)=1$。
• 如果 $p$ 是质数，$\mu(p) = -1$。
• 如果 $i \% p_j \neq 0$，$\mu(i \cdot p_j) = -\mu(i)$。
• 如果 $i \% p_j = 0$，$\mu(i \cdot p_j) = 0$。

代码实现

题意概括: 使用线性筛，计算并存储 $1$ 到 $N$ 所有数的莫比乌斯函数值。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1000005;
bool isp[N];
int p[N / 10];
int mu[N];
int cnt;

void sieve(int n) {
    memset(isp, 0, sizeof(isp));
    isp[0] = isp[1] = 1;
    mu[1] = 1;

    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) { // i是质数
            p[cnt++] = i;
            mu[i] = -1; // mu(p) = -1
        }
        for (int j = 0; j < cnt && (ll)i * p[j] <= n; ++j) {
            int np = p[j];
            isp[i * np] = 1;
            if (i % np == 0) { // i的最小质因子是np
                mu[i * np] = 0; // 含有平方因子
                break;
            } else { // i和np互质
                mu[i * np] = -mu[i];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    sieve(n);
    // 打印前20个莫比乌斯函数值作为示例
    for (int i = 1; i <= min(n, 20); ++i) {
        cout << "mu(" << i << ") = " << mu[i] << endl;
    }
    return 0;
}

• 复杂度分析：与标准线性筛完全相同，时间复杂度和空间复杂度均为 $O(N)$。

5. 例题

5.1 选择题

1. 使用埃氏筛筛选出 $100$ 以内的所有质数，数字 $30$ 会被哪些质数筛掉？ A. 2 B. 3 C. 5 D. 2, 3, 5

   解析： 在标准的埃氏筛法中（未经优化的版本），一个合数会被它的所有质因子筛选。$30$ 的质因子为 $2, 3, 5$。

   • 当外层循环到质数 $2$ 时，会标记所有 $2$ 的倍数，因此 $30 = 2 \times 15$ 会被标记。
   • 当外层循环到质数 $3$ 时，会标记所有 $3$ 的倍数，因此 $30 = 3 \times 10$ 会被标记。
   • 当外层循环到质数 $5$ 时，会标记所有 $5$ 的倍数，因此 $30 = 5 \times 6$ 会被标记。 因此，$30$ 会被其所有质因子 $2, 3, 5$ 筛掉。 答案：D

2. 线性筛法的时间复杂度是？ A. $O(N \log N)$ B. $O(N \log \log N)$ C. $O(N)$ D. $O(N \sqrt{N})$

   解析： 线性筛法的核心思想是确保每个合数都只被其最小质因子筛选一次。由于每个数只被访问常数次，总的时间复杂度是线性的。 答案：C

3. 在线性筛算法中，对于任意一个合数 $N$，它被标记为合数时，是基于以下哪种分解？ A. $N = i \times p$，其中 $p$ 是 $N$ 的任意一个质因子 B. $N = i \times p$，其中 $p$ 是 $N$ 的最大质因子 C. $N = i \times p$，其中 $p$ 是 $N$ 的最小质因子 D. $N = p_1 \times p_2$，其中 $p_1, p_2$ 均为质数

   解析： 线性筛的关键代码 if (i % p[j] == 0) break; 保证了当程序执行 v[i * p[j]] = 1; 来标记合数时，p[j] 一定是合数 i * p[j] 的最小质因子。 答案：C

4. 下列哪个函数不是积性函数？ A. 欧拉函数 $\varphi(n)$ B. 莫比乌斯函数 $\mu(n)$ C. 恒等函数 $id(n) = n$ D. 最小质因子函数 $spf(n)$

   解析： 积性函数的定义是：对于任意两个互质的正整数 $a, b$，有 $f(ab)=f(a)f(b)$。 A, B, C 均为常见的积性函数。 D: 最小质因子函数 $spf(n)$ (Smallest Prime Factor)。我们可以用一个反例来检验。令 $a=2, b=3$，它们互质。 $spf(2)=2$, $spf(3)=3$。则 $f(a)f(b) = 2 \times 3 = 6$。 但是 $ab=6$， $spf(6)=2$。 因为 $spf(6) \neq spf(2) \times spf(3)$，所以 $spf(n)$ 不是积性函数。 答案：D

5.2 判断题

1. 在经过优化的埃氏筛中（内层循环从 $i^2$ 开始），合数 $15$ 会被质数 $3$ 筛掉。 ( √ )

   解析： 优化的埃氏筛，外层循环遍历到质数 $i$ 时，内层循环从 $i \times i$ 开始标记。当外层循环 $i=3$ 时，内层循环会标记 $3 \times 3=9, 3 \times 4=12, 3 \times 5=15, \dots$。因此，$15$ 会被质数 $3$ 筛掉。 答案：√

2. 在线性筛中，当处理到 $i=12$ 时，内层循环会因为 12 % 2 == 0 而在检查完质数 $2$ 后立即 break。 ( √ )

   解析： 当外层循环进行到 $i=12$ 时，已找到的质数列表 p 为 $2, 3, 5, 7, 11, \dots$。内层循环从最小的质数 p[0]=2 开始。

   • j=0, p[0]=2。程序标记合数 12 * 2 = 24。
   • 随后检查 if (i % p[j] == 0)，即 if (12 % 2 == 0)。该条件成立。
   • 执行 break，内层循环终止。 因此，程序不会再用质数 $3, 5, \dots$ 去乘 $12$。 答案：√

3. 任何积性函数都可以在 $O(N)$ 的时间内用线性筛预处理出来。 ( × )

   解析： 该说法是错误的。虽然许多常见的积性函数（如欧拉函数 $\varphi(n)$、莫比乌斯函数 $\mu(n)$、约数个数函数 $d(n)$）都可以用线性筛高效计算，但这并非普遍规律。能够使用线性筛求解一个积性函数 $f(n)$ 的前提是，我们必须能够高效地（通常是 $O(1)$ 时间）通过 $f(i)$ 和 $f(p_j)$ 的值推导出 $f(i \times p_j)$ 的值（需要分别处理 $i$ 与 $p_j$ 互质和不互质两种情况）。对于某些复杂的积性函数，这种递推关系可能不存在，或者计算非常耗时，导致无法实现线性时间复杂度的预处理。 答案：×

5.3 程序阅读题

题目：阅读下面的C++代码，并回答问题。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100;
int p[N], f[N];
bool v[N];
int cnt;

void solve(int n) {
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) {
            v[i] = 1;
            p[cnt++] = i;
            f[i] = 2;
        }
        for (int j = 0; j < cnt && (ll)i * p[j] <= n; ++j) {
            v[i * p[j]] = 1;
            if (i % p[j] == 0) {
                // some logic here
                break;
            } else {
                f[i * p[j]] = f[i] * f[p[j]];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve(50);
    cout << f[12] << endl;
    return 0;
}

1. 该程序实现的算法框架是？
2. 变量 f[i] 试图存储的是数字 i 的什么数论函数值？
3. 为了让程序正确计算该函数，// some logic here 处应该填入什么代码？
4. main 函数在当前代码下（即 // some logic here 为空）最终会输出什么？

解析：

1. 算法框架： 代码具有 for (int i...) { if (!v[i]) {...} for (int j...) {... if(i%p[j]==0) break;} } 的标志性结构，这毫无疑问是线性筛（或称欧拉筛）的算法框架。

2. 函数值： 我们来分析 f 函数的性质：

   • 当 i 是一个质数 p 时，代码设置 f[i] = 2。
   • 当 i 和质数 p[j] 互质时 (i % p[j] != 0)，代码执行 f[i * p[j]] = f[i] * f[p[j]]。这正是积性函数的定义。 一个在质数 p 处取值为 $2$ 的积性函数，最常见的就是约数个数函数 $d(n)$（因为一个质数 p 只有 $1$ 和 p 两个约数）。因此，可以推断该程序试图计算并存储每个数字的约数个数。

3. 补全代码： 原代码的主要问题在于 if (i % p[j] == 0) 的分支是空的。在这种情况下，$d(i \times p_j)$ 的值无法仅从 $d(i)$ 和 $d(p_j)$ 推导出来，必须知道 $i$ 中最小质因子 $p_j$ 的指数。 标准的线性筛求约数个数需要引入一个辅助数组，我们称之为 g[i]，记录 $i$ 的最小质因子 $p_j$ 的指数加一。 完整的递推逻辑如下：

   • 当 i 是质数时: f[i] = 2, g[i] = 2。
   • 当 i % p[j] != 0 时 (互质): f[i * p[j]] = f[i] * f[p[j]] = f[i] * 2。此时 i * p[j] 的最小质因子是 p[j]，指数为1，所以 g[i * p[j]] = 2。
   • 当 i % p[j] == 0 时 (不互质): 设 $d(i) = \frac{f(i)}{g(i)} \times g(i)$。$i \times p_j$ 相比 $i$，只是最小质因子 $p_j$ 的指数加了1。所以 $d(i \times p_j) = \frac{d(i)}{g(i)} \times (g(i)+1)$。 所以 // some logic here 应该替换为：

   // 假设 g[] 是辅助数组
   f[i * p[j]] = f[i] / g[i] * (g[i] + 1);
   g[i * p[j]] = g[i] + 1;
   

4. main 函数输出： 在未经修改的原始代码中，// some logic here 是空的。我们来追踪 f[12] 的计算过程：

   • f[1] 被初始化为 1。
   • f[2]=2, f[3]=2, f[5]=2, ...
   • 当 i=2, j=0, p[j]=2 时，i % p[j] == 0 成立，执行 break。f[4] 的值从未被计算。
   • 当 i=3, j=0, p[j]=2 时，i % p[j] != 0 成立，计算 f[6] = f[3] * f[2] = 2 * 2 = 4。
   • 为了计算 f[12]，程序需要执行到 i=6, j=0, p[j]=2。此时 i % p[j] == 0 成立，执行 break，f[12] 未被计算。或者执行到 i=4，但 f[4] 根本没有值。 由于 f 是一个全局数组，未被赋值的元素会被默认初始化为 0。因为代码逻辑的缺陷，f[12] 始终不会被赋值。因此，程序最终会输出其初始值。 输出: 0

   如果代码被修正，f[12] 的值会被正确计算出来：$d(12) = d(2^2 \times 3^1) = (2+1) \times (1+1) = 6$。

5.4 程序补全题

题意概括: 下面的代码使用线性筛计算 $1$ 到 $N$ 所有数的最小质因子 spf[i]。请补全 ___1___, ___2___, ___3___, ___4___ 四处空白。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1000005;
int p[N / 10];
int spf[N];
bool v[N];
int cnt;

void sieve(int n) {
    v[0] = v[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!v[i]) {
            p[cnt++] = i;
            ___1___; // 当i是质数时
        }
        for (int j = 0; j < cnt && (ll)i * p[j] <= n; j++) {
            v[___2___] = 1;
            spf[i * p[j]] = ___3___;
            if (i % p[j] == 0) {
                ___4___;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    sieve(1000000);
    cout << "spf[99] = " << spf[99] << endl;
    cout << "spf[100] = " << spf[100] << endl;
    return 0;
}

解析与答案:

1. ___1___: 在 if (!v[i]) 块中，i 被确定为一个质数。一个质数的最小质因子就是它自身。所以此处应填 spf[i] = i;。
2. ___2___: 内层循环的目的是标记合数。当前正在处理的合数是 i 和质数 p[j] 的乘积，所以需要标记 v[i * p[j]]。此处应填 i * p[j]。
3. ___3___: 线性筛保证了任何合数 N = i * p[j] 都是被其最小质因子 p[j] 筛掉的。所以 i * p[j] 的最小质因子就是 p[j]。此处应填 p[j]。
4. ___4___: 这是线性筛的核心机制。当 i 是 p[j] 的倍数时，意味着 p[j] 是 i 的最小质因子。此时必须 break 循环，以防止后续更大的质数 p[j+1] 去筛选 i，从而保证每个合数只被其最小质因子筛一次。此处应填 break;。

补全后代码: ___1___: spf[i] = i; ___2___: i * p[j] ___3___: p[j] ___4___: break;

main函数输出:

• 对于 $99$，其质因数分解为 $3^2 \times 11$。它的最小质因子是 $3$。所以 spf[99] 的值是 3。
• 对于 $100$，其质因数分解为 $2^2 \times 5^2$。它的最小质因子是 $2$。所以 spf[100] 的值是 2。

埃氏筛 ($O(N \log \log N)$)：思想简单直观，易于实现。通过标记质数的倍数为合数来筛选。虽然存在重复标记，但效率已经非常高，足以应对大部分百万级别数据规模的质数筛选问题。

线性筛 ($O(N)$)：通过精巧的设计，保证每个合数仅被其最小质因子筛选一次，达到了理论最优的线性时间复杂度。其核心思想不仅能用于求质数，更能推广到在线性时间内预处理各种积性函数（如欧拉函数、莫比乌斯函数等），是解决更复杂数论问题的基石。