GESP 八级 · GESP 202512 C++ 八级 第 10 题

下列程序实现了线性筛法（欧拉筛），用于在 $O(n)$ 时间内求出 $1 \sim n$ 之间的所有质数。为了保证每个合数只被其最小质因子筛掉，横线处应填入的语句是（ ）。

for (int i = 2; i <= n; i++) {
    if (!not_prime[i]) primes[++cnt] = i;
    for (int j = 1; j <= cnt && i * primes[j] <= n; j++) {
        not_prime[i * primes[j]] = true;
        if (________) break; // 在此处填入选项
    }
}

埃氏筛法：从2开始标记倍数为合数，O(n log log n)。线性筛（欧拉筛）：每个合数只被最小质因子标记一次，O(n)。线性筛效率更高。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】素数筛法｜线性筛原理｜O(n) 时间复杂度

考纲定位：本题落在《GESP 考试大纲》CSP‑J/S 八级"算法与数据结构"模块的数论部分，专门考查"线性筛法（欧拉筛）"。命题人放这道题，就是要卡住那些只会背结论、却说不清"为什么每个合数只被最小质因子筛掉"的考生。

解题思维：线性筛的核心是"每个合数只被其最小质因子筛掉一次"。外层循环枚举 i，内层用 primes 数组里的质数去筛 i 的倍数。j <= cnt && i * primes[j] <= n 保证筛的范围不超过 n，当 i % primes[j] == 0 时，primes[j] 就是 i 的最小质因子，此时 i * primes[j] 已经被筛过，必须停止内层循环，否则后面更大的质数会重复筛掉这个合数，复杂度退化为 O(n log log n) 甚至更差。因此横线处应填 i % primes[j] == 0。

陷阱拆解：A 项 i + primes[j] == n 是偷换概念，把乘法筛法混成加法筛法，逻辑完全跑偏；B 项 primes[j] > i 看似合理，实则条件永远成立（primes 递增且 i 从 2 起），会导致内层循环提前结束，漏筛大量合数；D 项 i % primes[j] != 0 正好相反，会无限循环使算法退化成普通埃氏筛，时间复杂度变回 O(n log log n)。这些陷阱利用考生对线性筛条件的记忆模糊，或者对"最小质因子"的理解偏差。

反命题思维：如果把条件改成 i % primes[j] != 0，就变成了普通埃氏筛，命题人显然不会这么改，因为那样就失去了线性筛的优势；或者把外层循环改成从 3 开始，那样会漏掉 2 这个质数，命题人可能想考边界条件。提醒学生：刷到类似题，先问自己"命题人想考我什么"。