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

下面埃氏筛从 i * i 开始标记，是因为 i * i 之前的 i 的合数倍数已经被更小的质因子标记过。

for (int i = 2; (long long)i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}

看到筛法先想：质数倍数标记范围。核心观察是"小于 i² 的 i 倍数必有更小的质因子"，因此从 i² 开始能避免重复标记。这类题通法：先定位算法框架，再分析优化条件，最后用反例验证边界。

选 B 的人常误以为必须从 2i 开始，忽略了 2i 已被质因子 2 标记。命题人用"i² 之前"的绝对化表述，正是利用考生对筛法细节不熟，把优化条件当成普通起点。

1. 考纲定位

本题考查 GESP 五级"数论基础"模块中的埃氏筛法优化。命题人卡住的是考生对"为什么从 i² 开始"的直觉缺失——多数人会机械套用"从 2i 开始"，却不知 i² 之前的 i 倍数必含更小质因子。

2. 解题思维

看到筛法先想：质数倍数标记范围。核心观察是"小于 i² 的 i 倍数必有更小的质因子"，因此从 i² 开始能避免重复标记。

用数值验证：i=5 时，i²=25，25 之前的 5 的倍数有 10、15、20。10=2×5 被 2 标记，15=3×5 被 3 标记，20=2×10 被 2 标记——确实都被更小的质因子覆盖。

这类题通法：先定位算法框架，再分析优化条件，最后用反例验证边界。