c++ - 而 (i<=sqrt(static_cast(n))

Question

在“C++ without Fear: A Beginner's Guide That Makes You Feel Smart”一书中的第 (2) 章：Decisions, Decisions 中，您可以将这行代码视为素数程序的一部分：

while (i<=sqrt(static_cast<double>(n))

前提是“i”被初始化为“2”，而“n”是用户的输入。

为什么我们要比较“n”的“sqrt”而不是“n”本身？

谢谢。

score 6 · Accepted Answer

因为你不会得到任何大于 sqrt(n) 的非素数因子（你已经找到了另一个更小的因子）。

虽然这是一个非常糟糕的测试，但最好将其编写为：

while (i*i <= n)

score 3 · Accepted Answer

因为如果一个数字有除自身和 1 以外的因子，那么这些因子中至少有一个会小于该数字的 sqrt。

score 0 · Accepted Answer

从算法上讲，检查可能的因素直到目标的平方根是正确的。

如果 N 是一个可能是素数也可能不是素数的数，如果在 sqrt(N) 之前没有因子（不包括 1），那么 N 必须是素数。sqrt(N) 本身很可能是它唯一的主要因素（例如 9，即 3*3）。

如果我们要测试 17 是否为素数，我们知道 sqrt(17) 刚好在 4 之上。2、3 和 4 不能整除 17，所以它必须是素数，因为 5 更大。

一定是这样，因为 17/5 将小于 5，并且也必须是一个因数，但我们知道没有小于 5 的因数。

以编程方式当然代码不是最佳的，因为您不会使用双精度和平方根，而是使用 (i*i <= N)

score 0 · Accepted Answer

while (i<=sqrt(static_cast<double>(n))

相当于

while(n >= i*i)

作者为什么选择第一种解决方案可能取决于代码的其他部分。

score 0 · Accepted Answer

代码如下：

i = 2;
while (i <= sqrt(static_cast<double>(n)) {
  if (n % i == 0) is_prime = false;
  i++;
}

所以循环正在检查n是否可以被i整除而没有余数。显然，只需要检查（并包括） n的平方根（因为如果n / p = qthen 也是n / q = p）。

5 回答 5