C语言素数判断程序输入整数2时判定非素数的问题排查

错误根因 #

原程序prime_check函数存在核心逻辑缺陷：

• 输入值为2时，for循环初始值i=2，循环判定规则为i < number，即2 < 2结果为假，循环体一次都不会执行
• 对数值2的素数判断写在了循环体内部，循环不触发的情况下该判断永远不会生效；且循环执行完成后函数没有明确的返回值，会返回内存中的随机垃圾值，实际运行时该值不为0，就被主函数判定为非素数
• 额外隐藏bug：原循环内只要第一次取余运算不成立就直接返回“是素数”的结果，比如判断9、15这类奇数合数时，会因为不能被2整除直接误判为素数，只是之前测试没有覆盖到这类场景。

修正后的完整代码 #

调整边界值判断顺序，把小于2的非法值、特殊素数2的判断放在循环外，只有遍历完所有可能的因子都没有找到整除项时，才返回“是素数”的结果：

#include <stdio.h>
#include <stdlib.h>

// 返回值规则：1=非素数，0=素数
int prime_check(int number) {
    // 小于2的数全部不是素数
    if (number < 2) {
        return 1;
    }
    // 2是唯一的偶素数，直接返回结果
    if (number == 2) {
        return 0;
    }
    // 遍历查找是否存在能整除的因子
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            return 1;
        }
    }
    // 所有可能因子遍历完成无整除项，判定为素数
    return 0;
}

int main() {
    int user_n;
    printf("pls enter the number\n");
    scanf("%d", &user_n);
    if (prime_check(user_n) == 0) {
        printf("the number is prime\n");
    } else {
        printf("its not prime..\n");
    }
    return 0;
}

可选性能优化 #

判断因子时不需要遍历到number-1，只需要遍历到sqrt(number)即可（因子成对出现，大于平方根的因子必然对应一个小于平方根的因子），把循环条件修改为i * i <= number就能大幅减少大数值判断时的循环次数。

内容的提问来源于stack exchange，提问作者Blghn