GESP 五级 · GESP 202403 C++ 五级 第 9 题

下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。（ ）

bool isPrime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i * i < num; ++i) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

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

注意德摩根律的正确应用：┐(A∧B)=┐A∨┐B，┐(A∨B)=┐A∧┐B。C++中逻辑运算符有短路求值特性。

1. 🎯 考纲定位

素数判断｜循环条件优化｜GESP 五级

命题人专门挖了个数学边界坑——考查你是否真正理解"素数只需试除到平方根"的原理。绝大多数考生背过模板却忽略细节，导致循环范围算错。

2. 🧠 解题思维

素数判断的核心是：一个数若有因子，必存在一个因子 ≤ sqrt(num)。因此只需枚举 i 从 2 到 floor(sqrt(num)) 检查整除性。

代码中 i * i < num 等价于 i < sqrt(num)，这意味着当 i 达到 sqrt(num) 时循环提前终止。以 num=4 为例：i=2 时 i*i=4，条件 4<4 为假，循环不执行，直接返回 true——把合数 4 误判为素数。

正确做法是 i * i <= num，这样 i 能达到 sqrt(num)，能检测到 2 这个因子。