java - 如何找到第五个完美数(即33550336)？这个问题需要永远的解决

Question

我正在尝试编写一个Java方法来检查数字是否为完美数字。
理想数是一个等于其所有除数(不包括其自身)之和的数字。
例如，6是一个完美的数字，因为1+2+3=6。然后，我必须编写一个Java程序以使用该方法显示前5个完美数字。
除了这个问题，我没有任何问题，因为它永远需要第五个完美数字33550336。
我知道这是因为isPerfectNumber()方法中的for循环。但是，我对编码非常陌生，我不知道如何提出更好的代码。

public class Labreport2q1 {

  public static void main(String[] args) {
    //Display the 5 first perfect numbers
    int counter = 0,
    i = 0;

    while (counter != 5) {
      i++;
      isPerfectNumber(i);
      if (isPerfectNumber(i)) {
        counter++;
        System.out.println(i + " ");
      }
    }

  }

  public static boolean isPerfectNumber(int a) {
    int divisor = 0;
    int sum = 0;
    for (int i = 1; i < a; i++) {
      if (a % i == 0) {
        divisor = i;
        sum += divisor;
      }
    }

    return sum == a;

  }

}

This is the output that is missing the 5th perfect number

Answer 1

让我们检查一个完美数字的属性。 This Math Overflow question告诉我们两个非常有趣的事情:

一个完美的数字永远不会是一个完美的平方。

理想数字的形式为(2k-1)×(2k-1)。

第二点很有趣，因为它使我们的搜索范围几乎没有。 Java中的int是32位。在这里，我们看到了功率和位位置之间的直接关系。多亏了这一点，而不是对isPerfectNumber进行数百万次的调用，我们将少于32个来找到第5个完美的数字。
因此，我们已经可以更改搜索字段，这就是您的主要循环。

    int count = 0;
    for (int k = 1; count < 5; k++) {

      // Compute candidates based on the formula.
      int candidate = (1L << (k - 1)) * ((1L << k) - 1);

      // Only test candidates, not all the numbers.
      if (isPerfectNumber(candidate)) {
        count++;
        System.out.println(candidate);
      }
    }

这是我们的重大胜利。没有其他优化可以胜过这一点:为什么要测试3,300万个数字，而您却可以测试少于100个数字？
但是，即使我们有了很大的改进，您的应用程序整体还是可以改进的，即您的方法isPerfectNumber(int)。
目前，您仍在测试太多数字。一个完美的数字是所有适当除数的总和。因此，如果d除以n，则n/d也除以n。您可以一次添加两个除数。但是美丽之处在于您可以在sqrt(n)处停止，因为sqrt(n)*sqrt(n) = n在数学上是可以的。因此，仅测试n除数，而不是测试sqrt(n)除数。
同样，这意味着您必须开始考虑极端情况。极端情况是1和sqrt(n):

1是一个特例，因为如果将n除以1，则会得到n，但无需添加n即可检查n是否为理想数字。您只添加1。因此，我们可能会从1开始求和，以避免出现过多的if。

sqrt(n)是一个极端的情况，因为我们必须检查sqrt(n)是否为整数，并且它很乏味。但是我提到的数学溢出问题说，没有完美的数字是一个完美的平方，因此可以简化我们的循环条件。

然后，如果sum大于n，我们可以停止。适当的除数之和大于n表示n丰富，因此不是完美的。这是一个很小的进步，但实际上很多候选人都很丰富。因此，如果保留它，您可能会节省几个周期。
最后，我们必须注意一个小问题:将1作为候选者。 1是第一个候选人，它将通过我们的所有测试，因此我们必须为此做一个特殊的案例。我们将在方法开始时添加该测试。
现在，我们可以将方法编写如下:

  static boolean isPerfectNumber(int n) {
    // 1 would pass the rest because it has everything of a perfect number
    // except that its only divisor is itself, and we need at least 2 divisors.
    if (n < 2) return false;
   

    // divisor 1 is such a corner case that it's very easy to handle:
    // just start the sum with it already.
    int sum = 1;

    // We can stop the divisors at sqrt(n), but this is floored.
    int sqrt = (int)Math.sqrt(n);

    // A perfect number is never a square.
    // It's useful to make this test here if we take the function
    // without the context of the sparse candidates, because we
    // might get some weird results if this method is simply
    // copy-pasted and tested on all numbers.
    // This condition can be removed in the final program because we
    // know that no numbers of the form indicated above is a square.
    if (sqrt * sqrt == n) {
      return false;
    }
    
    // Since sqrt is floored, some values can still be interesting.
    // For instance if you take n = 6, floor(sqrt(n)) = 2, and
    // 2 is a proper divisor of 6, so we must keep it, we do it by
    // using the <= operator.
    // Also, sqrt * sqrt != n, so we can safely loop to sqrt
    for (int div = 2; div <= sqrt; div++) {
      if (n % div == 0) {
        // Add both the divisor and n / divisor.
        sum += div + n / div;
        // Early fail if the number is abundant.
        if (sum > n) return false;
      }
    }
    return n == sum;
  }

这些优化使得您甚至可以在一秒钟内找到第七个完美数字，只要您将代码改写为long而不是int即可。而且您仍然可以在30秒内找到第8名。
这是该程序(test it online)。我删除了评论，因为上面的解释在这里。

public class Main {
  public static void main(String[] args) {
    int count = 0;
    for (int k = 1; count < 8; k++) {
      long candidate = (1L << (k - 1)) * ((1L << k) - 1);
      if (isPerfectNumber(candidate)) {
        count++;
        System.out.println(candidate);
      }
    }
  }

  static boolean isPerfectNumber(long n) {
    if (n < 2) return false;
    long sum = 1;
    long sqrt = (long)Math.sqrt(n);
    for (long div = 2; div <= sqrt; div++) {
      if (n % div == 0) {
        sum += div + n / div;
        if (sum > n) return false;
      }
    }
    return n == sum;
  }
}

上面程序的结果是前8个完美数字的列表:

6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128

您可以找到进一步的优化，特别是在搜索中是否检查2k-1是否为Eran says in their answer为素数，但是鉴于long的候选对象少于100个，我发现潜在地增加几毫秒的有用性并不大因为在此程序中，计算素数也可能很昂贵。如果您想检查更大的理想素数，这是有道理的，但是在这里？否:这会增加复杂性，因此我尝试使这些优化相当简单直接。