GESP 八级 · GESP 202503 C++ 八级 第 11 题

下面的欧氏筛法程序中，两个横线处应填入的分别是（ ）。

int primes[MAXP], num = 0;
bool isPrime[MAXN + 1] = {false};
void sieve() {
    for (int n = 2; n <= MAXN; n++) {
        if (!isPrime[n]) {
            primes[num++] = n;
            for (int i = 0; i < num && ________; i++) { // 在此处填入选项
                isPrime[n * primes[i]] = true;
                if (________) // 在此处填入选项
                    break;
            }
        }
    }
}

A.

n * primes[i] < MAXN
n % primes[i] == 0

B.

n * primes[i] < MAXN
primes[i] > n

C.

n * primes[i] <= MAXN
n % primes[i] == 0

D.

n * primes[i] <= MAXN
primes[i] > n

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

注意德摩根律的正确应用：┐(A∧B)=┐A∨┐B，┐(A∨B)=┐A∧┐B。C++中逻辑运算符有短路求值特性。

【考点】筛法优化｜循环边界判断｜欧氏筛法

1. 🎯 考纲定位

GESP 八级《算法模块》第 4 章"筛法与数论"，卡在循环边界条件与欧氏筛经典优化两个考点的交叉处。命题人专挑学生最易混淆的地方下手——把 <= 写成 <、把优化条件写乱。