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
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]].
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.