Projekt Euler # 23

Question

ich zur Zeit versucht, das Projekt euler Problem Nummer 23 zu lösen:

Eine perfekte Zahl ist eine Zahl, für die die Summe ihrer echten Teiler ist genau gleich der Zahl. Zum Beispiel wäre die Summe der richtigen Teiler von 28 1 + 2 + 4 + 7 + 14 = 28, was bedeutet, dass 28 eine perfekte Zahl ist.

Eine Zahl n heißt mangelhaft, wenn die Summe ihrer Eigendivisoren kleiner als n ist, und sie wird als reichlich bezeichnet, wenn diese Summe n übersteigt.

Da 12 die kleinste reichliche Zahl ist, 1 + 2 + 3 + 4 + 6 = 16, ist die kleinste Zahl, die als Summe zweier reichlich vorhandener Zahlen geschrieben werden kann, 24. Durch mathematische Analyse kann gezeigt werden Alle ganzen Zahlen größer als 28123 können als die Summe von zwei reichlich vorhandenen Zahlen geschrieben werden. Diese Obergrenze kann jedoch durch die Analyse nicht weiter reduziert werden, obwohl bekannt ist, dass die größte Zahl, die nicht als Summe zweier reichlich vorhandener Zahlen ausgedrückt werden kann, geringer ist als diese Grenze.

Finden Sie die Summe aller positiven ganzen Zahlen, die nicht als die Summe zweier reichlich vorhandener Zahlen geschrieben werden können.

Allerdings gibt mein Code kein korrektes Ergebnis, obwohl es völlig in Ordnung zu sein scheint. Berechnen ich mehr als genug Zahlen?

private static void Main() 
    { 
     List<int> AbudantNumbers = new List<int>(); 
     long sum = 0; 
     for (int i = 12; i <= 28123; i++) 
     { 
      int abudantNumber = GetProperDivisor(i); 
      if (abudantNumber > i) 
      { 
       AbudantNumbers.Add(i); 
      } 
     } 

     for (int k = 1; k <= 28123; k++) 
     { 
      int count = 0; 
      for (int i = 0; i < AbudantNumbers.Count; i++) 
      { 
       count = 0; 
       if (AbudantNumbers[i] > k) 
       { 
        break; 
       } 
       for (int j = i; j < AbudantNumbers.Count; j++) 
       { 
        if (AbudantNumbers[j] > k) 
        { 
         break; 
        } 
        if (AbudantNumbers[i] + AbudantNumbers[j] == k) 
        { 
         count++; 
         break; 
        } 
       } 
      } 
      if (count == 0) 
      { 
       sum += k; 
      } 
     } 
     Console.WriteLine(sum); 
     Console.ReadKey(); 
    } 

    private static int GetProperDivisor(int input) 
    { 
     int sum = 1; 
     for (int i = 2; i <= input/2; i++) 
     { 
      if (input%i == 0) 
      { 
       sum += i; 
      } 
     } 
     return sum; 
    } 

Mein Ergebnis ist: 297.632.990 richtiges Ergebnis: 4179871

Ganz großer Unterschied, wenn es keine offensichtlichen Fehler in meinem Code sind.

Mein zweiter Ansatz:

 for (int k = 1; k <= 28123; k++) 
     { 
      var k1 = k; 
      int count = 
       (from t1 in AbudantNumbers.TakeWhile(t1 => t1 <= k1) let a = t1 select t1).Count(
        t1 => AbudantNumbers.TakeWhile(t => t <= k).Any(t => t1 + t == k)); 
      if (count == 0) 
      { 
       sum += k; 
      } 
     } 

Meine Idee ist, als 28123 alle reichlich Zahlen weniger zu bekommen als alle Zahlen überprüfen weniger als 28.123 (alles über eine Summe von 2 reichlich Zahlen) als drehen alle reichlich Zahlen und zuletzt überprüfen, ob abundantNumber1 + abundantNumber2 == currentNumber wenn ja, wir brechen aus der Schleife, weil wir nur diejenigen brauchen, die keine Summe von 2 reichlich vorhandenen Zahlen haben.

Answer 1

Wenn Sie feststellen, dass die aktuelle Anzahl k die Summe von zwei reichlich Zahlen a[i] + a[j], stellen Sie die count und dann brechen aus der Schleife – aus der inneren Schleife über j, das ist.

Das bedeutet, dass Sie immer noch alle verbleibenden i s betrachten, für die Sie die count zurücksetzen. Effektiv betrachten Sie nur die letzte reichlich vorhandene Zahl, die kleiner oder gleich k ist. Es ist nicht wahrscheinlich, dass die Summe der beiden Zahlen diese Zahl beinhaltet, daher wird Ihre Bedingung für das Hinzufügen der Zahlen count == 0 in den meisten Fällen falsch sein.

Sie müssen aus den zwei innersten Schleifen ausbrechen, wenn Sie herausfinden, dass k == a[i] + a[j]. C# scheint keine Schleifen zu haben, daher ist es wahrscheinlich am besten, die inneren Schleifen in eine Funktion umzuwandeln, die die Liste der reichlich vorhandenen Zahlen und k als Argumente annimmt; Sie können dann einfach true zurückgeben, wenn Ihre Bedingung erfüllt ist.

Als schnelle, aber hässlich zu beheben, können Sie

if (count) break; 

nach der Schleife über j hinzufügen.

Ihre Vorgehensweise ist jedoch sehr ineffektiv. Es könnte besser sein, nur zwei verschachtelte Schleifen über alle im Überfluss vorhandenen Zahlen zu schreiben und dann ihre Summen zu einer Menge hinzuzufügen, wenn sie kleiner als 28124 sind. Dann addieren Sie alle Zahlen von 1 bis 28124, die nicht in der Menge sind.