寻找完美数字（优化）

Question

作为编程挑战的一部分，我用 C# 编写了一个程序来查找特定范围内的完美数字。然而，我意识到计算 10000 以上的完美数时速度非常慢。是否有任何优化方法可以找到完美数？我的代码如下：

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleTest
{
 class Program
 {
  public static List<int> FindDivisors(int inputNo)
  {
   List<int> Divisors = new List<int>();
   for (int i = 1; i<inputNo; i++)
   {
    if (inputNo%i==0)
     Divisors.Add(i);
   }
   return Divisors;
  }

  public static void Main(string[] args)
  { 
   const int limit = 100000;

   List<int> PerfectNumbers = new List<int>();
   List<int> Divisors=new List<int>();
   for (int i=1; i<limit; i++)
   {
    Divisors = FindDivisors(i);
    if (i==Divisors.Sum())
     PerfectNumbers.Add(i);
   }

   Console.Write("Output =");

   for (int i=0; i<PerfectNumbers.Count; i++)
   {
    Console.Write(" {0} ",PerfectNumbers[i]);
   }

   Console.Write("\n\n\nPress any key to continue . . . ");
   Console.ReadKey(true);
  }
 }
}

Answer 1

使用公式

测试完美 = 2^n-1(2ⁿ - 1)

生成可能性，然后检查该数字是否实际上是完美的。

试试这个睡前读物

Answer 2

完美数会改变吗？不。看这里。当然，它们应该计算一次然后存储。在你的情况下，唯一的结果将是

下一个是33550336。超出了你的范围。

Answer 3

我说的很明显：你不需要检查每个除数。寻找

inputNo/2

之后的除数是没有意义的。这减少了一半的计算量，但这并没有快一个数量级。

Answer 4

解决此类问题的一种方法是在内存中为每个数字构建一个巨大的数组，然后将数字划掉。

Answer 5

如果您仍在寻找计算完美数字的东西。前一万的速度很快，但 3300 万的速度有点慢。

public class Perfect {
private static Perfect INSTANCE = new Perfect();

public static Perfect getInstance() {
    return INSTANCE;
}

/**
 * the method that determines if a number is perfect;
 * 
 * @param n
 * @return
 */
public boolean isPerfect(long n) {
    long i = 0;
    long value = 0;
    while(++i<n){
        value = (0 == n%i?value+i:value);
    }
    return n==value;
}
}

Answer 6

对于任何对基于 LINQ 的方法感兴趣的人，以下方法对我来说非常有效且有效，可以确定调用者提供的整数值是否是完美数字。

bool IsPerfectNumber(int value)
{
    var isPerfect = false;

    int maxCheck = Convert.ToInt32(Math.Sqrt(value));
    int[] possibleDivisors = Enumerable.Range(1, maxCheck).ToArray();
    int[] properDivisors = possibleDivisors.Where(d => (value % d == 0)).Select(d => d).ToArray();
    int divisorsSum = properDivisors.Sum();

    if (IsPrime(divisorsSum))
    {
        int lastDivisor = properDivisors.Last();
        isPerfect = (value == (lastDivisor * divisorsSum));
    }

    return isPerfect;
}

为了简单和清晰起见，省略了我在 IsPerfectNumber() 中使用的 IsPrime() 实现。

Answer 7

继续 Charles Gargent 的回答，有一种非常快速的方法可以检查梅森数（又称为 2^n - 1）是否是素数。它被称为 Lucas-Lehmer 测试基本的伪代码（取自维基百科页面）是：

// Determine if Mp = 2p − 1 is prime for p > 2
Lucas–Lehmer(p)
    var s = 4
    var M = 2p − 1
    repeat p − 2 times:
        s = ((s × s) − 2) mod M
    if s == 0 return PRIME else return COMPOSITE

Answer 8

一个不算太多……

发现至少存在一个奇完全数，并通过一些数学发明来做到这一点。历史上，曾有过关于数学是发明还是发现的争论，但由于毫无结果的争论而被放弃。尽管如此，如果辩论的结果很重要怎么办？如果数学是发现而不是发明，并且我们不完美的数学发明（按照完美数）阻止了我们做出数学发现，但是，如果我们通过更好的数学发明纠正这些不完美的发明，我们可能会发现潜在的数学发现事实是，至少有一个奇完全数？

令 n 为任何自然数，可以表示为另外两个自然数 a 和 b 的乘积，因此 n = a x b，其中 a 小于或等于 b。

因此 6 = 1 x 6 或 6 = 2 x 3，但是，6 = 1 x 2 x 3 未被考虑。

所以 8 = 1 x 8 或 8 = 2 x 4，但是，8 = 2 x 2 x 2 没有被考虑。

因此，完美数 6 和 28 分别具有以下相关因子 a 和 b 的有序对，n = 6 或 n = 8….(1, 6), (2, 3) 对于 n = 6 ，以及 (1, 8), (2, 4)（n = 8）。

而非完美数 5 的双因子因子（其中 a 小于或等于 b 且 a x b = n）的相关有序对为 (1, 5)，而非完美数 5 的相关有序对为 (1, 5) 10 具有相关的双因子因子有序对，如 (1, 10) 和 (2, 5)。

因此，一个完美数，例如 6 或 28，其相关的双因子因子有序对的总和等于 2n。换句话说，1 + 6 + 2 + 3 = 2 x 6，而 28 的双因子因子的相关有序对的总和为 1 + 28 + 2 + 14 + 4 + 7 = 2 x 28。

而对于非完美数（例如 5 或 10），其双因子的相关有序对的总和分别不等于 2 x 5 或 2 x 10。

因此，完美数 p 的双因子因子的相关有序对的总和等于 p 值的两倍，而对于非完美数则并非如此。

根据这个定义，1 是一个完美数，作为其有序对的双因子因子 1 + 1 = 2 x 1 之和。那么 1 是一个奇完美数，并且适合欧拉-欧几里得构造根据 1 = (2^(k-1))((2^k)-1) 对于 k = 1。

Shaul Ben-Yimini（[电子邮件受保护]）

寻找完美数字（优化）

问题描述投票：0回答：8

8个回答

最新问题

寻找完美数字（优化）

问题描述 投票：0回答：8

8个回答

最新问题

问题描述投票：0回答：8