Mittel 0 gelöst 0% Erfolgsquote

Befreundete Zahlen

Liste alle Paare befreundeter Zahlen auf, deren beide Zahlen höchstens eine gegebene Grenze erreichen.

Das lernst du

  • Eine Tabelle der echten Teilersummen für alle Zahlen bis zu einer Grenze aufbauen
  • Eine Paarbedingung in beide Richtungen prüfen
  • Kein Paar doppelt und keine vollkommenen Zahlen auflisten

Problem

Sei s(n) die Summe der echten Teiler von n (also aller Teiler außer n selbst). Zwei verschiedene Zahlen a und b bilden ein Paar befreundeter Zahlen, wenn s(a) = b und s(b) = a gilt. Das kleinste Paar ist 220 und 284: s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 und s(284) = 1 + 2 + 4 + 71 + 142 = 220.

Implementiere amicable_pair(limit).

s(n) für jedes n bis limit einzeln zu berechnen ist langsam. Besser geht es mit einem Sieb: Addiere für jedes d den Wert d zu jedem Vielfachen von d, das größer als d ist.

Eingabe

limit: Der größte Wert, den eine der beiden Zahlen eines Paares haben darf.

Ausgabe

Gib eine Liste von Paaren [a, b] mit a < b ≤ limit zurück, aufsteigend nach a sortiert. Ein Paar wird nur aufgenommen, wenn beide Zahlen höchstens limit sind. Vollkommene Zahlen (mit s(n) = n) bilden kein Paar. Gibt es keine Paare, gibst du eine leere Liste zurück.

Einschränkungen

1 ≤ limit ≤ 200.000

Beispiele

Beispiel 1
Eingabe:
limit = 1500

Erwartete Ausgabe:
expected = [
    [220, 284],
    [1184, 1210]
]
Eingabe:
long long limit = 1500;

Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
Eingabe:
long limit = 1500;

Erwartete Ausgabe:
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

Erläuterung

s(220) = 284 und s(284) = 220, außerdem s(1184) = 1210 und s(1210) = 1184. Beide Paare liegen unter 1500: [[220, 284], [1184, 1210]].

Beispiel 2
Eingabe:
limit = 250

Erwartete Ausgabe:
expected = []
Eingabe:
long long limit = 250;

Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {};
Eingabe:
long limit = 250;

Erwartete Ausgabe:
long[][] expected = new long[][] {};

Erläuterung

220 ist höchstens 250, sein Partner 284 aber nicht, also passt kein Paar: [].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Addiere für jedes d von 1 bis limit / 2 den Wert d zu den Summen von 2d, 3d, 4d und so weiter.

Hinweis 2

Sei b für jedes a dessen Teilersumme; prüfe, ob b im erlaubten Bereich liegt und ob die Teilersumme von b gleich a ist.

Hinweis 3

Mit der Bedingung a < b wird jedes Paar nur einmal aufgelistet und vollkommene Zahlen fallen weg.

Erwartete Komplexität

Zeit O(limit log limit), zusätzlicher Speicher O(limit)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.