Die Suche nach perfekten Zahlen (Optimierung)

Question

I codierte ein Programm in C # bis zu perfekten Zahlen innerhalb eines bestimmten Bereichs als Teil einer Programmierung Herausforderung zu finden. Aber ich merkte, dass es sehr langsam ist, wenn vollkommene Zahlen nach oben von 10000. Berechnung Gibt es Methoden der Optimierung, die für die Suche nach perfekten Zahlen gibt es? Mein Code ist wie folgt:

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

Verwenden Sie die Formel

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

erzeugen possiblities dann überprüfen, ob die Zahl in der Tat perfekt ist.

versuchen, dies für einige Bettlektüre

Answer 2

Do perfekte Zahlen ändern? Nr Schauen Sie hier . Sicherlich sollten sie einmal berechnet und dann gespeichert. In Ihrem Fall sind die einzigen Ergebnisse sein

6
28
496
8128

Der nächste ist 33550336. Außerhalb Ihres Bereich.

Answer 3

Genau das offensichtlichste von mir: Sie brauchen nicht jeden Teiler zu überprüfen. Kein Punkt der Suche nach Teilern Vergangenheit inputNo/2. Dass verkürzt sich die Hälfte der Berechnungen, aber dies ist nicht eine Größenordnung schneller.

Answer 4

Eine Möglichkeit, Dinge zu lösen, wie dies beinhaltet den Aufbau eine große Array im Speicher jeder Zahl, und dann Kreuzung Zahlen aus.

Answer 5

, wenn Sie noch auf der Suche nach etwas, perfekten Zahlen zu berechnen. dies geht durch die ersten zehntausend ziemlich schnell, aber die 33 Millionen-Zahl ist ein wenig langsamer.

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

Für jedermann in einem LINQ basierten Ansatz interessierte, arbeitete das folgende Verfahren recht gut und effizient für mich bei der Bestimmung, ob ein Anrufer geliefert Integer-Wert eine perfekte Zahl ist.

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

Aus Gründen der Einfachheit und Klarheit, meine Implementierung für IsPrime (), die innerhalb IsPerfectNumber () verwendet wird, weggelassen wird.

Answer 7

Um von Charles Gargent Antwort weiterhin eine sehr schnelle Art und Weise ist zu überprüfen, ob eine Mersenne-Zahl auch bekannt als 2 ^ n - 1 eine Primzahl ist. Es ist der Lucas-Lehmer-Test genannt Der Grund Pseudo-Code aber (aus der Wikipedia-Seite weitergeleitet) ist:

// 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