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

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

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

    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            ______________________ {  // 在此处填入代码
                is_prime[j] = false;
            }
        }
    }

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

    return primes;
}

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

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

【考点】埃拉托斯特尼筛法｜素数判定｜循环优化

1. 考纲定位 本题考查 GESP 五级算法模块中"素数筛法"的核心实现细节。绝大多数五级考生卡在"i*i"优化上——要么死记硬背为2i，要么凭感觉填i，其实这是筛法时间复杂度从O(n²)降到O(n log log n)的数学关键。

2. 解题思维 埃氏筛法的本质是：对每个素数i，标记它的所有倍数。但小于i²的i的倍数，必定含有比i更小的素因子（如i·2、i·3等），早已被标记过。因此只需从i²开始标记，步长设为i。代码中外层循环到sqrt(n)正是利用这个事实——大于sqrt(n)的合数必被其最小素因子筛掉，不必再处理。

3. 陷阱拆解 A：j++会标记i+1、i+2等非i倍数的数，彻底破坏筛法逻辑；B：j++仍会标记非倍数，且j从i²开始没必要覆盖i²到2i-1这段本可被更小素数筛掉的区域；D：j从i开始会重复标记i本身（is_prime[i]已为true），浪费操作且违背筛法语义。C的"i*i起始+j+=i"是唯一同时满足正确性、完整性和最优性的写法。

4. 反命题思维 若题目改为"统计小于等于n的素数个数"，只需在筛完后count(is_prime[i])即可，复杂度从O(n)降到O(√n)。类似题先问自己：这道题考的是筛法原理、时间优化还是计数技巧——命题人把"i*i"放在横线就是专门测试你是否理解筛法的数学本质，而非机械记忆模板。