GESP 五级 · GESP202609 C++ 五级 第 6 题

下面代码实现线性筛法。为了保证每个合数只被其最小质因子筛去一次，横线处应填写（　　）。

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

线性筛的核心是保证每个合数只被其最小质因子筛去一次。外层循环 i 是待筛数，内层 p 遍历已存质数。当 i % p == 0 时，p 已是 i 的最小质因子，i * p 的最小质因子仍为 p，此时 i * p 已在之前被标记（当处理 i 时），故需 break。这一条件同时保证了筛法的 O(n) 复杂度。

A 项 p % i == 0 是反向判断，当 i > p 时恒假，导致 i * p 被重复筛；C 项 i == p 仅处理 i 为质数时，i = 6 时 p = 2, 3 均不触发；D 项 i * p == n 是边界条件，与筛法逻辑无关。最阴险的是"保证每个合数只被其最小质因子筛去一次"这一表述，考生易忽略"最小质因子"的隐含条件。

考纲定位

本题考查 GESP 五级"算法与数据结构"模块的线性筛法。命题人卡住的是"为何每个合数只被筛一次"这一本质，绝大多数考生会背下模板却说不清 break 条件的数学依据。

解题思维

看到线性筛先想"最小质因子唯一性"。外层循环 i 是待筛数，内层 p 遍历已存质数。i * p 必为合数，但必须保证 p 是 i * p 的最小质因子。若 i % p == 0，则 p 已是 i 的最小质因子，i * p 的最小质因子仍为 p，此时 i * p 已在之前被标记（当处理 i 时），故需 break。数值推演：i = 6 时 primes = [2, 3, 5]，p = 2 满足 6 % 2 == 0，6 * 2 = 12 已在 i = 2 时标记；p = 3 满足 6 % 3 == 0，6 * 3 = 18 已在 i = 3 时标记；p = 5 不满足，6 * 5 = 30 首次标记。