0

不久前，我得到了一个关于如何编写 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函数工作!=吗？

谢谢。

4

2 回答 2

2

不。在测试一个数是否为素数时，你知道它不是只要你找到一个因素。

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

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

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

于 2012-12-26T12:13:36.160 回答
1

不，这是不可能的。

如果找到一个因素，这个原始代码就具有提前返回的能力。修改后的版本在找到因素时会提前返回。由于您必须测试所有可能的因素（至少，小于平方根的因素），然后才能确定该数字不是素数，因此您提出的方法无法工作。

附带说明一下，一个小的变化可以使算法的效率几乎翻倍。由于我们不必测试任何大于 2 的偶数，我们可以先测试 2，然后以 3 开始循环并递增 2s：

bool prime(int x)
{
  if (x < 2) return false;
  if (x%2 == 0) return x == 2;
  for(int i=3; i<= sqrt(x); i+=2) {
    if ((x%i) == 0) return false;
  }
  return true;
}
于 2012-12-26T12:14:09.297 回答