为什么需要检查 sqrt(n) 以内的值以确定数字的除数
Why is it required to check for values upto sqrt(n), to determine divisors of a number
我一直在寻找确定数字除数的最有效方法。我发现一篇文章提到，不是从 1 upto n 开始迭代，而是可以通过从 1 upto sqrt(n) 开始迭代来减少总体 运行 时间，如果假设 1<=k<=sqrt(n) 和 [=13] =] 是数字 n 的约数，那么另一个约数将是 n/k.
有没有数学证明为什么我们只需要迭代到 sqrt(n)?
如果你有一个除数 d >sqrt(n)，那么它的余数 n/d 将小于 n/sqrt(n) 等于 sqrt(n) 所以你已经找到了n/d 在你的算法结束时，因此也是 n/(n/d)，也就是 d。
我一直在寻找确定数字除数的最有效方法。我发现一篇文章提到，不是从 1 upto n 开始迭代，而是可以通过从 1 upto sqrt(n) 开始迭代来减少总体 运行 时间，如果假设 1<=k<=sqrt(n) 和 [=13] =] 是数字 n 的约数，那么另一个约数将是 n/k.
有没有数学证明为什么我们只需要迭代到 sqrt(n)?
如果你有一个除数 d >sqrt(n)，那么它的余数 n/d 将小于 n/sqrt(n) 等于 sqrt(n) 所以你已经找到了n/d 在你的算法结束时，因此也是 n/(n/d)，也就是 d。