关于C++质数判断代码中while循环与sqrt函数的疑问

开发者阿泽

2026-6-20

质数判断代码中while循环的作用解释

先还原《C++ Without Fear（第三版）》里这类质数判断的典型代码结构（你遇到的应该是类似版本）：

bool is_prime(int n) {
    if (n <= 1)
        return false;
    int i = 2;
    while (i * i <= n) {
        if (n % i == 0)
            return false;
        i++;
    }
    return true;
}

为什么必须用while循环，而非单个if？

质数的核心定义是：大于1的自然数，除了1和自身之外没有任何其他正因数。要确认n是质数，必须检查所有2到√n之间的整数——只要有一个数能整除n，它就不是质数。
单个if语句只能检查某一个固定的i（比如只检查i=2），这完全不够。举个例子：判断n=9时，单个if检查i=2会得到9%2≠0，错误认为9是质数，但实际上9能被3整除，是合数。
while循环的作用就是遍历所有可能的除数i：从2开始，每次递增1，直到i的平方超过n（这里的优化逻辑是：如果n有一个大于√n的因数，那对应的另一个因数必然小于√n，所以检查到√n就足够覆盖所有可能的因数）。
循环里的if是做单次检查：每拿到一个i，就判断n能否被它整除。如果能，直接返回false（确认不是质数）；如果不能，就i++继续检查下一个数。当整个循环跑完都没找到能整除n的i，就说明n符合质数定义，返回true。