C++素数判断程序误将9、15判定为素数的代码错误排查

原代码核心逻辑错误 #

• 模运算对象错误：循环内判断整除时固定写为n%2==0，没有使用循环变量i，全程只校验了数字能否被2整除，完全没检查其他除数
• 判定时机完全错误：素数/合数的输出逻辑放在循环内部，第一次迭代（i=2）时只要数字不能被2整除，就会因为flag初始值为0直接判定为素数并跳出循环，根本不会遍历后续可能的因子，这就是9、15等奇合数被误判的直接原因
• 循环边界冗余：即使逻辑正确，循环上界设为i<=n也会产生大量无效计算，素数判断不需要遍历到数字本身
• 边界场景缺失：没有处理n<2（0、1、负数）的输入场景，这类输入会得到完全错误的结果

误判复现示例 #

以输入n=9为例：循环启动后i=2，判断9%2==0结果为假，直接进入else分支；此时flag仍为初始值0，程序直接输出"9 is a prime number"后break终止，根本不会执行i=3的整除校验，自然出现误判。

修正后可运行代码 #

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n;
    cout << "Enter the number : ";
    cin >> n;
    
    // 小于2的数必然不是素数
    if (n < 2) {
        cout << n << " is a non-prime number";
        return 0;
    }

    bool is_prime = true;
    // 遍历到sqrt(n)即可覆盖所有可能的因子，减少无效计算
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            is_prime = false;
            break;
        }
    }

    // 遍历完所有可能因子后再输出结果
    if (is_prime) {
        cout << n << " is a prime number";
    } else {
        cout << n << " is a non-prime number";
    }
    return 0;
}

修正说明 #

• 修复模运算逻辑，循环内通过n%i==0判断当前遍历值是否为n的因子
• 把结果输出逻辑移到循环外部，只有完整遍历完所有可能的因子、没有找到任何整除项时，才判定为素数
• 优化循环上界为sqrt(n)，降低计算量：如果n存在大于sqrt(n)的因子，其对应的配对因子必然小于sqrt(n)，不需要重复校验
• 补充n<2的边界处理，覆盖0、1、负数等异常输入场景

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