GESP 五级 · GESP 202509 C++ 五级 第 7 题

函数 linearSieve 实现线性筛法 (欧拉筛)，横线处应填入（ ）。

vector<int> linearSieve(int n) {
    vector<bool> is_prime(n+1, true);
    vector<int> primes;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i]) primes.push_back(i);
        for(int p : primes) {
            if(p * i > n) break;
            is_prime[p * i] = false;
            if(________) break;
        }
    }
    return primes;
}

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

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

<model_info>
Model: by
</model_info>
【考点】线性筛法｜素数判定
【正确答案】A

线性筛的核心在于保证每个合数仅由其最小质因子筛出。外层枚举 i，内层用已存质数 p 筛去合数 p·i；当 p 不再是最小质因子时，同一合数会被重复标记，时间复杂度退化为 O(n log log n)。因此必须在中途截断内层循环。

正确写法是 `i % p == 0`。此时 p 恰好是 i 的最小质因子，p·i 的最小质因子就是 p，筛法能确保每个合数只被生成一次，实现 O(n) 线性时间。若写成 `p % i == 0`（B），只在 p 被 i 整除时截断，而 i 通常远大于 p，导致几乎不触发 break，失去线性性质；写成 `i == p`（C）则内层仅执行一次，大量合数未被筛去；写成 `i * p == n`（D）则循环在到达 n 时才停止，同样无法避免重复标记。

命题人特意把条件放在 `break` 之前，考察对"最小质因子"这一抽象概念的理解，而非死记硬背代码。若把条件改为 `i % p != 0`，则失去线性性质，退化为普通筛法；若把 `break` 移到条件之后，则会出现重复筛除，导致结果错误。

刷到类似题时，先问自己："我要保证每个合数只被最小质因子筛一次，那什么时候停止内层循环？"