寻找完美数（优化）

StackOverflow https://stackoverflow.com/questions/2651573

题

我编写了在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);
  }
 }
}
有帮助吗？

解决方案

使用公式

testPerfect = 2n-1(2n - 1)

以产生possiblities然后检查阉羊数目实际上完美的。

尝试这对于一些睡前阅读

其他提示

待办事项完美数的变化？ 看这里。当然，他们应该再进行计算，然后存储。 在你的情况下，唯一的结果将是

6
28
496
8128

下一个是33550336.外您的范围。

刚刚从我明显的：你并不需要检查每一个除数。没有点寻找除数过去inputNo/2。这将切断计算的一半，但这不是一个数量级的速度更快。

要解决这样的事情涉及建立一个庞大的阵列中的每个号码的存储器中，然后交叉数出的一种方式。

如果你还在寻找的东西来计算完美的数字。 这种经过第一10000相当快，但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;
}
}

有关感兴趣的人在基于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;
}

为了简单和清楚起见，我的用于IsPrime（），其内IsPerfectNumber（）中使用，实施被省略。

要从查尔斯Gargent的答案继续有一个非常快速的方法来检查，如果梅森数又名2 ^ N - 1是素数。这就是所谓的卢卡斯 - 莱默测试 基本伪代码虽然（从维基百科页面采取）是：

// 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
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top