GESP 五级 · GESP 202506 C++ 五级 第 25 题

如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为 $O(n)$。

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

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

        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
    return primes;
}

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

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

【考点】线性筛法原理｜时间复杂度分析｜内层循环break条件

1. 🎯 考纲定位

GESP 五级算法模块，考查"素数筛法优化"。命题人卡住的是大量背过埃氏筛却误以为"线性筛只需去掉重复筛"的学生——他们完全没理解为什么内层必须 break。