GESP 七级 · GESP 202506 C++ 七级 第 14 题

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

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²)，要看内层是否每次都在缩小。

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

1. 🎯 考纲定位

本题定位在《GESP 七级》算法复杂度分析模块，属于数论与算法结合的高频考点。命题人专门设计这道题，就是要考你识别"线性筛"这一经典算法，并理解其时间复杂度优于普通埃氏筛（$O(n\log\log n)$）的本质。