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

下面的代码用于判断整数 $n$ 是否是质数，错误的说法是（ ）。

bool is_prime(int n) {
    if (n <= 1) return false;

    int finish_number = static_cast<int>(sqrt(n)) + 1;
    for (int i = 2; i < finish_number; ++i) {
        if (n % i == 0)
            return false;
    }
    return true;
}

质数判定优化：只需检查2到√n。偶数除了2都不是质数。判断素数的时间复杂度O(√n)。

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

【考点】质数判断算法｜埃氏筛法｜线性筛法

1. 🎯 考纲定位

本题考查《GESP 五级大纲》"算法效率与优化"模块中的质数判定的三种主流算法。命题人卡住的是考生对算法复杂度与适用场景的混淆——五级考生普遍死记"筛法更快"这个结论，却不懂何时该用筛法、何时该用试除法。