GESP 八级 · GESP 202403 C++ 八级 第 12 题

下面程序的时间复杂度为（ ）。

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {
    for (int n = 2; n <= MAXN; n++) {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
            isPrime[n * primes[i]] = true;
            if (n % primes[i] == 0)
                break;
        }
    }
}

质数判定优化：只需检查2到√n。偶数除了2都不是质数。判断素数的时间复杂度O(√n)。

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

【考点】线性筛｜时间复杂度分析｜素数判定

本题在 GESP 八级算法模块中属于"素数筛法"类题，命题人想卡住考生对"经典埃氏筛"与"欧拉线性筛"复杂度差异的模糊认识。

解题需先识别代码为线性筛：外层循环 n 从 2 到 MAXN，内层枚举已存素数并标记合数，且 n % primes[i] == 0 时立即 break，保证每个合数仅被其最小质因子筛掉一次。因此总操作次数≈n 次，时间复杂度 O(n)。

陷阱在于：若误以为所有筛法都是 O(n log log n)（经典埃氏筛），就会选 C；若忽略内层 break 条件，会误判为 O(n log n) 或 O(n²)。只有紧扣"每个合数只被标记一次"这一本质，才能得出 O(n)。

反命题：若去掉 break 条件，该筛退化为经典埃氏筛，复杂度变为 O(n log log n)；若内层改为枚举所有倍数且不加 break，则每个合数被重复标记多次，复杂度升至 O(n log n)。刷到类似筛法题时，先问自己"本题是否保证了每个合数只被筛一次"。