GESP 五级 · GESP 202406 C++ 五级 第 7 题

下述代码实现素数表的线性筛法，筛选出所有小于等于 $n$ 的素数，则横线上应填的代码是（ ）。

vector<int> linear_sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        ________________________ { // 在此处填入代码
            is_prime[i * primes[j]] = 0;
            if (i % primes[j] == 0)
                break;
        }
    }
    return primes;
}

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

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

【考点】线性筛法｜素数判定｜时间复杂度分析

命题人卡住的是考生对"每个合数只被最小质因子筛一次"这一核心机制的理解，而非单纯套模板。

看到 break 后立刻意识到这是线性筛的核心——保证每个合数只被最小质因子筛一次。因此内层循环必须遍历所有满足 i * primes[j] <= n 的素数 primes[j]，若仅到 sqrt(n) 会漏掉最小质因子大于 sqrt(n) 的合数，导致时间复杂度退化。

选项B和D的 j <= sqrt(n) 是命题人精心设计的陷阱——若按此循环，每个合数会被多个质因子重复筛（例如 6 = 2×3 和 6 = 3×2 都被筛），导致时间复杂度退化为 O(n sqrt(n))。选项C的 j <= n 更离谱，不仅效率低下，还会因 primes[j] 越界（primes 只有 n 个素数）而崩溃。

若把 break 条件改为 i % primes[j] != 0（即不停止），内层循环仍为 j < primes.size() && i * primes[j] <= n，则每个合数会被其所有质因子重复筛，退化为埃氏筛的 O(n log log n) 版本；若再删掉 break 仅保留 j <= sqrt(n)，则会漏筛大量合数，导致结果错误。