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

埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是（ ）。

vector<int> eratosthenes_sieve(int n) {
    vector<bool> is_composite(n + 1, false);
    vector<int> primes;

    for (int i = 2; i <= n; i++) {
        if (is_composite[i]) continue;

        primes.push_back(i);

        for (long long j = (long long)i * i; j <= n; j += i)
            is_composite[j] = true;
    }
    return primes;
}

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

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】埃氏筛优化｜最小质因子｜时间复杂度分析

考纲定位：本题对应 GESP 五级"算法设计"模块中经典的数论筛法优化考点。命题人专门挖这个坑，就是卡住那些只背"i*i 是合数"结论、却不懂"合数必有最小质因子 ≤ sqrt(n)"的学生。

解题思维：看到 i*i 起手，先问：为什么不是 2*i？关键观察是：任何形如 k*i（k < i）的数，必然存在一个质因子 p ≤ k < i。这个 p 在更外层循环时已经被筛过，所以 k*i 其实早就被标记为合数了。

陷阱拆解：逐个排除：A 错（2×3=6 是合数），B 错（4=2²是合数），D 错（埃氏筛复杂度是 O(n log log n)，不是 O(n)）。只有 C 是本质原因——小于 i*i 的 i 的倍数，其最小质因子一定小于 i，已被更小的质数筛过。

反命题思维：如果把 i*i 改成 2*i，就会重复标记大量数，但复杂度从 O(n log log n) 变成 O(n log n)；改成 i*i-1 会漏掉 i*i 本身。这类题先问"如果起点提前/延后会发生什么"，就能抓住命题人想考的"必要性"。