下面 sieve 函数的时间复杂度为：
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; // 保证每合数只筛一次
}
}
}
- A. O(n)
- B. O(n log log n)
- C. O(n log n)
- D. O(n²)
正确答案：A