GESP 五级 · GESP 202512 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)。线性筛效率更高。

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

【考点】线性筛法（欧拉筛）｜vector遍历边界控制｜素数判定逻辑

线性筛的核心是确保每个合数只被其最小质因数筛掉一次。枚举质数 primes[j] 时，必须从 j=0 开始遍历，因为 primes[0] 就是素数 2；循环条件必须包含 i*primes[j]<=n 的边界检查，否则当 i 较大时会产生越界访问。选项 A 的起始下标 j=0 正确，且条件 j<primes.size() 配合 i*primes[j]<=n 既保证遍历完整又防止溢出，完全匹配算法结构。选项 B 从 sqrt(n) 开始枚举是严重错误，会遗漏一半以上的素数，破坏筛法逻辑；C 项 j 从 1 开始且上限 sqrt(n) 双错；D 项 j 起始错误且缺少对 primes 大小的判断。如果你只背"线性筛要 break"却不懂循环条件设计，就会选错。

反命题思维：若题目改成"筛出所有大于等于 k 的素数"，则 primes 需先填充到 k，循环起始点要改为 j 使得 i*primes[j]>=k，边界条件仍要保留。刷到筛法变式，先问自己"这道题想让我验证什么"——是边界、是重复标记、还是漏筛？