GESP 八级 · GESP 202509 C++ 八级 第 10 题

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

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八级算法模块

🎯 考纲定位

GESP八级算法模块核心考点。命题人盯住的是"学生只背经典埃氏筛结论O(n log log n)，没真正理解线性筛的线性本质"——八级考生必须区分两种筛法，这是分水岭。