Problem
Die echten Teiler von n sind alle positiven Teiler außer n selbst. Für 12 sind das 1, 2, 3, 4 und 6. An ihrer Summe (auch Aliquotsumme genannt) erkennt man, ob eine Zahl vollkommen, abundant oder defizient ist. Teiler treten immer paarweise als d und n / d auf, deshalb musst du d nur bis zur Quadratwurzel von n durchprobieren.
Implementiere sum_of_proper_divisors(n).
Eingabe
n: Eine positive ganze Zahl.
Ausgabe
Gib die Summe aller positiven Teiler von n zurück, die kleiner als n sind. Für n = 1 gibt es keine, dann ist das Ergebnis 0.
Einschränkungen
1 ≤ n ≤ 10^12
Beispiele
Eingabe:
n = 12
Erwartete Ausgabe:
expected = 16
Eingabe:
long long n = 12;
Erwartete Ausgabe:
long long expected = 16;
Eingabe:
long n = 12;
Erwartete Ausgabe:
long expected = 16;
Erläuterung
1 + 2 + 3 + 4 + 6 = 16.
Eingabe:
n = 28
Erwartete Ausgabe:
expected = 28
Eingabe:
long long n = 28;
Erwartete Ausgabe:
long long expected = 28;
Eingabe:
long n = 28;
Erwartete Ausgabe:
long expected = 28;
Erläuterung
1 + 2 + 4 + 7 + 14 = 28, also ist 28 eine vollkommene Zahl.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Wenn d ein Teiler von n ist, dann ist auch n / d ein Teiler von n.
Hinweis 2
Probiere d nur bis zur Quadratwurzel von n und addiere jeweils beide Partner eines Paares.
Hinweis 3
Lass n selbst weg und addiere die Quadratwurzel nur einmal, wenn n eine Quadratzahl ist.
Erwartete Komplexität
Zeit O(sqrt n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.