为什么我们迭代到 root(n) 来检查 n 是否是一个完美的数字

Question

在检查数字 n 是否完美时，为什么我们要检查直到 (n) 的平方根？

也有人可以解释以下循环中的 if 条件

  for(int i=2;i<sqrt(n);i++)
  {
      if(n%i==0)
      {
          if(i==n/i)
          {
              sum+=i;  //Initially ,sum=1
          }
          else
          {
            sum+=i+(n/i);
          }
      }
  }

Answer 1

根据number theory，任何数至少有2个约数（1，数本身），如果数A是数B，则数B / A也是数B的约数。现在考虑一对数字 X，Y，使得 X * Y == B。如果X == Y == sqrt(B)，那么显然X, Y <= sqrt(B)。如果我们试图增加Y，那么我们必须减少X，这样他们的乘积仍然等于B.所以事实证明，在任何一对数字 X, Y 中，在乘积中给出 B，至少有一个数字是 <= 平方根（B）。因此，只需找到数字 B 的所有除数就足够了，其中 <= sqrt(B).

至于循环条件，那么sqrt(B)是数B的约数，但是我们B / sqrt(B)也是一个除数，它等于sqrt(B)，为了不把这个除数加上两次，我们这样写if （但你必须明白它永远不会被执行，因为你的循环完全达到 sqrt(n)）。

Answer 2

代码使用了一次找到两个因子的技巧，因为如果 i 除 n 那么 n/i 也除以 n，并且通常将它们相加（否则-条款）。

但是，您遗漏了代码中的错误：它在 i<sqrt(n) 期间循环，但有处理 i*i=n 的代码（then 子句 - 它应该只添加 i在这种情况下一次），这没有意义，因为这两个不能同时为真。

所以循环应该是<=sqrt(n)，即使没有完全平方数。（至少我还没有看到任何完全平方数，如果有一个简单的证明它们根本不存在我也不会感到惊讶。）

Answer 3

根据数论，这很简单：

如果 N 有一个因子 i，它也会有一个因子 n/i (1)
如果我们知道 1 -> sqrt(n) 中的所有因数，其余的可以通过应用 (1)

所以这就是为什么你只需要检查 1 -> sqrt(n)。但是，您的代码没有到达与i == sqrt(n)相同的子句i==n/i，因此如果N是一个完美的正方形，则不会计算sqrt(n)。

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n; cin >> n;
    int sum = 1;
    for(int i=2;i<sqrt(n);i++)
    {
        if(n%i==0)
        {
            if(i==n/i) { sum+=i; }
            else { sum+=i+(n/i); }
        }
    }
    cout << sum;
}

输入：9

输出：1

如您所见，完全遗漏了 3 = sqrt(9) 因素。要避免这种情况，请使用 i <= sqrt(n)，或避免使用 sqrt()，请使用 i <= n/i 或 i*i <= n.

编辑：

正如@HansOlsson 和@Bathsheba 提到的，没有奇数平方是完全数（很容易证明，甚至没有已知的奇数完全数），并且对于偶方，有证明here。所以在这种特殊情况下可以忽略 sqrt(n) 问题。

然而，在其他情况下，当您只需要遍历这些因素时，可能会出现一些错误。最好从一开始就使用正确的方法，而不是在将其用于其他用途时尝试跟踪错误。

相关 post : Why do we check up to the square root of a prime number to determine if it is prime?

为什么我们迭代到 root(n) 来检查 n 是否是一个完美的数字

why do we iterate to root(n) to check if n is a perfect number

c++

math

perfect-numbers