Problem
Die echten Teiler von n sind alle positiven Teiler außer n selbst. Vergleiche ihre Summe mit n: Ist die Summe größer, ist die Zahl abundant, ist sie gleich, ist die Zahl vollkommen (auch perfekt genannt), und ist sie kleiner, ist die Zahl defizient. Zum Beispiel sind die echten Teiler von 12 die Zahlen 1, 2, 3, 4 und 6, ihre Summe ist 16, also ist 12 abundant.
Implementiere abundant_perfect_deficient(n).
n kann bis zu 10^12 groß sein, daher ist es viel zu langsam, jede Zahl unterhalb von n zu prüfen. Teiler treten paarweise als d und n / d auf, du musst d also nur bis √n durchprobieren.
Eingabe
n: Die einzuordnende Zahl.
Ausgabe
Gib die Zeichenkette "abundant", "perfect" oder "deficient" in Kleinbuchstaben zurück. Die 1 hat keine echten Teiler (Summe 0) und ist daher defizient.
Einschränkungen
1 ≤ n ≤ 10^12
Beispiele
Eingabe:
n = 28
Erwartete Ausgabe:
expected = "perfect"
Eingabe:
long long n = 28;
Erwartete Ausgabe:
std::string expected = "perfect";
Eingabe:
long n = 28;
Erwartete Ausgabe:
string expected = "perfect";
Erläuterung
Die echten Teiler 1 + 2 + 4 + 7 + 14 ergeben zusammen 28, also lautet die Antwort "perfect".
Eingabe:
n = 15
Erwartete Ausgabe:
expected = "deficient"
Eingabe:
long long n = 15;
Erwartete Ausgabe:
std::string expected = "deficient";
Eingabe:
long n = 15;
Erwartete Ausgabe:
string expected = "deficient";
Erläuterung
Die echten Teiler 1 + 3 + 5 ergeben zusammen 9, das ist weniger als 15, also lautet die Antwort "deficient".
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 auch n / d; lass d nur laufen, solange d × d ≤ n gilt.
Hinweis 2
Wenn d × d = n ist, addiere d nur einmal, nicht zweimal.
Hinweis 3
Denk daran, n selbst nicht mitzuzählen, und behandle n = 1 gesondert.
Erwartete Komplexität
Zeit O(√n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.