GESP 五级 · GESP 202503 C++ 五级 第 6 题

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

vector<int> sieve_linear(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;

    if (n < 2) return primes;

    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n/2; i++) {
        if (is_prime[i])
            primes.push_back(i);

        for (int j = 0; _________________________ ; j++) {  // 在此处填入代码
            is_prime[ i * primes[j] ] = false;
            if (i % primes[j] == 0)
                break;
        }
    }

    for (int i = n/2 +1; i <= n; i++) {
        if (is_prime[i])
            primes.push_back(i);
    }

    return primes;
}

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

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

🎯 考纲定位

GESP 五级算法模块「筛法与递推」，命题人卡住的是嵌套循环里数组越界这个必考点。五级学生最容易只写 j < primes.size()，忽略内层乘积可能超 n，导致运行时错误。

🧠 解题思维

线性筛的核心：外层 2~n/2 遍历每个数 i，若 is_prime[i] 则入 primes；内层用已存素数 primes[j] 标记 i*primes[j] 为合数。终止条件必须同时满足两条：1）j 不超过素数表长度；2）乘积不超过 n。C 选项用逻辑与 && 短路求值，先判 j < primes.size() 再判乘积，安全且完整。

🪤 陷阱拆解

• A 只限 primes 边界，内层仍可能越界写入 is_prime，直接 Runtime Error。
• B 只限乘积，若 primes 尚未填满（例如 i 刚被加入），primes[j] 不存在，同样越界。
• D 用常数 n 作循环上限，primes[j] 会随机取到巨大值，双重越界。

最阴险的是 A 和 B 各对了一半，考生凭直觉选其一很容易掉坑。

🔄 反命题思维

命题人若把 is_prime 容量改成 n 并让内层从 j=0 开始，再删掉 if (i%primes[j]==0) break;，会退化成普通埃氏筛，时间复杂度从 O(n) 升到 O(n log log n)——这就是五级到四级常见的坑。刷到类似嵌套筛题，先问自己：内层循环的终止条件是否同时保护了索引和值域？