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

下面函数用于判断正整数 n 是否为质数。横线处的最佳写法是（　　）。

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

看到质数判断，第一反应是只需遍历到√n。因为若n有因子，必有一个≤√n。但i*i在int范围会溢出，必须用long long保证安全。

选项C看似简洁，却忽略了i*i可能溢出成负数，导致循环提前终止。选项A、B效率低，不符合"最佳"要求。

考纲定位

本题考查 GESP 五级"算法基础"模块中的质数判定与循环控制。命题人卡住的是考生对"平方根优化"与"整数溢出"的双重敏感度——绝大多数人只记得√n 优化，却忘了 i*i 在 32 位 int 上会溢出。

解题思维

看到 for (int i = 2; ...; i++) 立刻想到质数只需检查到 √n。若 n 有因子，必有一个 ≤ √n。因此循环条件应为 i * i <= n。但 i 是 int，当 n 接近 INT_MAX 时，i 可达 46340，i * i 会溢出成负数，使条件永远为假，导致错误返回 true。必须用 long long 保证乘法安全。