c++ - 对 bool prime 函数的轻微更改

Question

不久前，我得到了一个关于如何编写 bool 函数来检查数字是否为质数的问题的答案:bool function for prime numbers .

因此，有效的代码是

bool prime(int x)
{
if (x < 2) return false;
for(int i=2; i<= sqrt(x); i++) {
if ((x%i) == 0) return false;
}
return true;
}

但是，如果我将代码更改为

bool prime(int x)
{
if (x < 2) return false;
for(int i=2; i<= sqrt(x); i++) {
if ((x%i) != 0) return true;
}
return false;
}

它不能正确地确定一个数字对于许多整数来说是否是质数。我认为这两段代码是等价的。有没有办法让这个 bool prime 函数与 != 一起工作？

谢谢。

Answer 1

没有。在测试一个数是否为质数时，您知道它不是在您找到单个因数时就立即确定的。

这就是为什么您可以在第一个示例中尽早跳出 for 循环并返回 false 的原因:

if ((x%i) == 0) return false;

发现任何单个数字不是因数并不能证明数字是素数或非素数，因此您不能在这种情况下提前终止。