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

函数 sieve 实现埃拉托斯特尼筛法 (埃氏筛)，横线处应填入（ ）。

vector<bool> sieve(int n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i]) {
            for(int j = ______; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

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

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

【考点】数论基础｜埃拉托斯特尼筛法｜算法效率优化

考纲定位 GESP 五级"数论初步"模块的核心筛法题。命题人专门卡住考生对"起始点"的机械记忆——很多考生只背下 i*i 这个结论，却说不清为什么可以跳过更小的倍数，导致在考场上掉进"重复标记"的坑。

解题思维 筛法要标记合数。对素数 i，若从 i 或 2*i 开始，会错误把 i 自身或已标记的倍数再标一次。关键观察：小于 i*i 的 i 的倍数（2*i、3*i…）都已被更小的素数标记过。因此只需从 i*i 起，既避免重复，又保证正确。这是埃氏筛优化的数论依据。

陷阱拆解 A 从 i 起会把素数 i 标成 false，直接破坏筛法；B 从 i+1 起会漏掉 i 的倍数且仍可能重复；C 从 2*i 起会重复标记，效率减半。命题人利用考生对"起始点"的机械记忆，只背下 i*i 但不懂其背后的数论依据，导致掉坑。

反命题思维 若把题目改成"为什么从 i*i 开始"，或换一种考法问"线性筛的起始点如何确定"，答案会指向完全不同的底层原理。刷到类似题时，先问自己"命题人想考我什么底层原理"，而不是只背结论。