GESP 五级 · GESP 202606 C++ 五级 第 5 题

下面代码实现线性筛（欧拉筛），以筛选出 $n$ 以内的所有素数。横线处的代码应为（ ）。

vector<int> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    if (n >= 0) is_prime[0] = false;
    if (n >= 1) is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = false;
            if (________________) break; // 在此处填入代码
        }
    }
    return primes;
}

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

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】算法与数据结构｜线性筛（欧拉筛）｜最小质因子唯一性

线性筛的核心是"每个合数只被它的最小质因子筛掉一次"。外层 i 遍历所有数，内层用 primes[j] 去标记 i·primes[j]。关键观察：当 primes[j] 等于 i 时，i 就是当前合数的最小质因子，再继续乘更大的质数就会重复标记。因此 break 条件必须捕捉到"primes[j] 是 i 的因数且 i 不再更小"，即 i % primes[j] == 0。

选项 B 是 primes[j] % i == 0，反过来了，i 通常更大，这个条件几乎从不成立，内层循环无法提前退出，退化成慢的埃氏筛。选项 C 是 i % primes[j] != 0，非零条件完全相反，如果 i 不是 primes[j] 的倍数反而继续，逻辑错误。选项 D 是 i == primes[j]，看似对，但命题人特意用取模来测试你是否理解"最小质因子"概念，而非死记条件。最阴险的细节是"break 必须保证每个合数只被筛一次"，只背结论就会选 C 或 B。

站在命题人视角：若改成 i <= primes[j] 或 i < primes[j]，会怎样？i <= primes[j] 在 i 等于 primes[j] 时 break，和原题一样；i < primes[j] 则会在 i 小于 primes[j] 时 break，导致漏掉一些合数，比如 6 = 2·3，当 i=2, primes[j]=3 时，i < primes[j] 成立，会提前 break，6 没被标记。因此正确的 break 条件必须是 i % primes[j] == 0。

线性筛的时间复杂度 O(n) 源于每个合数只被访问一次。若 break 条件错误，内层循环会多跑，退化为 O(n·log log n) 的埃氏筛。这就是命题人特意用取模而非等号的原因——等号虽对，但取模更能体现"最小质因子"的本质。