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

下列 C++ 代码判断一个正整数是否是质数，说法正确的是（ ）。

bool is_prime(int n) {
    if (n <= 1)
        return false;
    if (n == 2 || n == 3 || n == 5)
        return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0)
        return false;

    int i = 7;
    int step = 4;
    int finish_number = sqrt(n) + 1;

    while (i <= finish_number) {
        if (n % i == 0)
            return false;
        i += step;
        step = 6 - step;
    }
    return true;
}

A. 代码存在错误，比如 $5$ 是质数，但因为 5 % 5 余数是 $0$ 返回了 false

B. finish_number 的值应该是 n / 2，当前写法将导致错误

C. 当前 while 循环正确的前提是：所有大于 $3$ 的质数都符合 $6k \pm 1$ 形式

D. while 循环修改如下，其执行效果和执行时间相同。

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

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

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

【考点】质数判定｜6k±1性质｜sqrt范围

1. 🎯 考纲定位

GESP 五级算法模块：数论基础（质数判定）。命题人刻意用看似复杂的循环结构，卡住只会背模板的学生——他们记"试除法到 sqrt(n)"，却不懂为什么从 7 开始且步长会变。