Problem 21: Befreundete Zahlen

Gesucht ist die Summe aller befreundeten Zahlen kleiner 10000! [ das englische Original ]

Unter befreundeten Zahlen versteht man ein Zahlenpaar, deren Summe aller ganzzahligen Teiler jeweils die anderen der beiden Zahlen ergibt. Die folgende Grafik zeigt ein solches Paar der Zahlen 220 und 284:

Die Zahlen 220 und 284 als Beispiel und Erklärung von "Befreundeten Zahlen"
Die Zahlen 220 und 284 als Beispiel und Erklärung von „Befreundeten Zahlen“

Da man für die Lösung des Problem offensichtlich die echten Teiler einer Zahl herausfinden muss, konnte ich hier den Algorithmus des Problem 12 wiederverwenden. Ich habe die Chance gleich einmal genutzt, um alle möglichen kleinen Hilfsfunktionen in einer eigenen Klasse im Helfer-Paket zu sammeln!

Auf Basis dieser Vorbereitung habe ich eine private Methode entwickelt, die testet, ob eine Zahl mit der Summe ihrer Teiler befreundet ist:

private boolean isAmicable( int num ) {
   if( cache.contains( num ) )
      return true;

   long sum = Mathe.getSumOfDivisors( num );

   if( sum != num && num == Mathe.getSumOfDivisors( sum ) ) {
      cache.add( sum );
      return true;
   } else {
      return false;
   }
}

Der verwendete Cache spart einiges an Zeit, da die berechneten Summen nicht noch einmal geprüft werden müssen. Damit kann das Problem selbst mit nur einer Schleife gelöst werden:

@Override
public String solve() {
   long sum = 0;
   int cur = 1;

   while( cur < 10000 ) {
      if( isAmicable( cur ) ) {
         sum += cur;
      }
      cur++;
   }

   return IO.l2s( sum );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 21 kann man sich hier anschauen!

<< Problem 20 Übersicht Problem 22 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: