GESP 五级 · GESP 202403 C++ 五级 第 10 题

在埃拉托斯特尼筛法中，要筛选出不大于 $n$ 的所有素数，最外层循环应该遍历什么范围（ ）？

vector<int> sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    std::vector<int> primes;
    ________________________
    {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

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

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

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

🎯 考纲定位

GESP 五级《算法与程序设计》第 3 章"算法基础"筛法部分。命题人把这道题放在五级，卡住的是大量二级考生——他们背过筛法流程，却不懂为什么外层只循环到 sqrt(n) 就够了，一到有 sqrt 就慌。