logo标签列表

如何找到第5个完美数（即33550336）？ 这个问题运行起来太慢了。

java
6

我正在尝试编写一个Java方法，检查一个数字是否是完全数。

完全数是指除本身外的所有因子之和等于该数的数。
例如，6是一个完美数，因为1+2+3=6。然后，我需要编写一个Java程序来使用这个方法来显示前5个完美数。

我遇到的问题是在我的isPerfectNumber()方法中for循环运行时间过长，这也导致获取第5个完美数33550336花费了很长时间。

我知道这是因为我的代码中的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;

  }

}

这是缺失第五个完全数的输出结果

你可以将for循环改为 for(int i =1; i <= (a/2); i++){...}，因为除数不能大于一半的数字。 - Turamarth
如果您的代码正确，问题可能是您需要等待足够长的时间。 - Alex Rmcf
2
你知道你在两次调用 isPerfectNumber 吗？一次是在 if 之前，另一次是在 if 中。结合 @Turamarth 的评论，这样可以加快速度。 - M. Deinum
1
请将您的图像托管多年作出保证，您能做到吗？ - NomadMaker
2个回答
8
让我们来检查一下完全数的性质。这个Math Overflow问题告诉我们两件非常有趣的事情：
  1. 完全数永远不是完全平方数。
  2. 完全数的形式为 (2k-1)×(2k-1)。
第二点非常有趣，因为它将我们的搜索范围减少到极小。在Java中，一个int是32位。而在这里，我们看到了幂和位位置之间的直接关系。由于这一点，我们只需要进行不到32次调用就能找到第5个完全数，而不是进行成百上千万次的isPerfectNumber调用。
因此，我们已经可以改变搜索范围，这就是你的主循环。
    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);
      }
    }

这里是我们的重大突破。没有其他优化能够超越它：为什么要测试3300万个数字，当你只需要测试不到100个呢？

尽管我们获得了巨大的提升，但你的整个应用程序仍然可以改进，即你的方法isPerfectNumber(int)。

目前，你仍然在测试过多的数字。完全数是所有真约数之和。因此，如果d除以n，n/d也除以n。你可以同时添加这两个约数。但美妙之处在于你可以停在sqrt(n)，因为从数学上讲sqrt(n)*sqrt(n) = n。所以你只需测试sqrt(n)个约数，而不是测试n个约数。

此外，这意味着你必须开始考虑边界情况。边界情况是1和sqrt(n)：

  • 1是一个边界情况，因为如果你将n除以1，你会得到n，但你不会添加n来检查n是否为完全数。你只添加1。因此我们可能会从1开始求和，以避免太多的if语句。
  • sqrt(n)是边界情况，因为我们必须检查sqrt(n)是否为整数，这很繁琐。但我参考的Math Overflow问题说没有完全数是完全平方数，所以这样可以简化我们的循环条件。

然后，如果在某个时刻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;
  }

这些优化技巧使得你甚至可以在一秒钟内找到第7个完美数，前提是你将代码改为使用long而不是int。并且你可以在30秒内找到第8个完美数。

所以这就是那个程序（在线测试）。我删除了注释，因为解释在上面。

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在他们的答案中所说，但考虑到我们对于long类型的候选人少于100个，我不认为在这个程序中潜在地节省几毫秒是有用的，因为计算质数也可能很昂贵。如果要检查更大的完美质数，那么这样做是有意义的，但在这里吗？不是的：它增加了复杂性，而我试图保持这些优化方法相对简单和直截了当。

谢谢您！然而，我不熟悉按位右移运算符>>的用法。在网上搜索后，我发现1 << n = 2^n。那么这是否意味着2L << (k-1) = 2L * 2^(k-1)？ - helia17
1
@helia17 你说得对，1 << n 等于 2<sup>n</sup>。在这种情况下，它之所以有效，是因为我总是使用2的幂，并且我的写作方式会使候选值 1 被跳过。我不应该那样做，我改回了 1 << n，并修复了 n <= 1 的 isPerfectNumber 方法。谢谢你的注意。 - Olivier Grégoire
3
有一些启发式方法可以从循环中提前退出，但是找到第五个完美数仍然花费了我几分钟的时间（我尝试了其他答案中建议的类似启发式方法）。
然而，你可以依靠欧拉的证明，所有偶完美数（仍然不知道是否存在奇完美数）都具有以下形式：
2i-1(2i-1)
其中 i 和 2i-1 都必须是质数。
因此，你可以编写以下循环来非常快速地找到前五个完美数：
int counter = 0,
i = 0;

while (counter != 5) {
    i++;
    if (isPrime (i)) {
        if (isPrime ((int) (Math.pow (2, i) - 1))) {
            System.out.println ((int) (Math.pow (2, i -1) * (Math.pow (2, i) - 1)));
            counter++;
        }
    }
}

输出：

6
28
496
8128
33550336

你可以在这里阅读更多关于它的内容。

如果你从int切换到long，你可以使用这个循环非常快地找到前7个完美数：

6
28
496
8128
33550336
8589869056
137438691328

我使用的isPrime方法是：

public static boolean isPrime (int a)
{
  if (a == 1)
    return false;
  else if (a < 3)
    return true;
  else {
    for (int i = 2; i * i <= a; i++) {
      if (a % i == 0)
        return false;
    }
  }
  return true;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接