寻找完美的数字（优化）

我用C＃编写了一个程序，以便在一定范围内找到完美的数字，作为编程挑战的一部分。 但是，我意识到计算10000以上的完美数字时速度非常慢。有没有找到完美数字的优化方法？ 我的代码如下：

using System; using System.Collections.Generic; using System.Linq; namespace ConsoleTest { class Program { public static List FindDivisors(int inputNo) { List Divisors = new List(); 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 PerfectNumbers = new List(); List Divisors=new List(); 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

使用公式

  testPerfect = 2 n-1 （2 n -  1） 

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

试试这个睡前阅读

Answer 2

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

 6 28 496 8128 

下一个是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 

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; } 

为简单起见，省略了IsPrifectNumber（）中使用的IsPrime（）实现。

Answer 7

为了继续查尔斯·加维特的回答，有一种非常快速的方法可以检查Mersenne数字是否为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