GESP 八级 · GESP 202606 C++ 八级 第 13 题

下列线性筛的代码片段中，当枚举到质数 p 且 i % p == 0 时，使用 break; 语句停止继续枚举。这样做的主要目的是（ ）。

for (int i = 2; i <= n; ++i) {
    if (!is_composite[i])
        primes.push_back(i);
    for (int p : primes) {
        if (i * p > n)
            break;
        is_composite[i * p] = true;
        if (i % p == 0)
            break;  // 这条语句的目的是？
    }
}

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

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】线性筛法｜最小质因子

1. 🎯 考纲定位

GESP 八级算法优化模块，筛法属于"数论算法"必考点。命题人卡的是"普通筛法能筛，但性能差"这个认知断层——九级才正式考线性筛，八级用线性筛代码挖坑，就是逼你提前掌握 $O(n)$ 筛法的底层逻辑，否则连 $2\times10^7$ 的数据量都过不了。