Problema
I divisori propri di n sono i suoi divisori positivi diversi da n stesso. Confronta la loro somma con n: se la somma è maggiore il numero è abbondante, se è uguale il numero è perfetto, se è minore il numero è difettivo. Per esempio i divisori propri di 12 sono 1, 2, 3, 4 e 6, la cui somma è 16, quindi 12 è abbondante.
Implementa abundant_perfect_deficient(n).
n può arrivare a 10^12, quindi provare tutti i numeri minori di n è decisamente troppo lento. I divisori vanno a coppie, d e n / d, perciò basta provare d fino a √n.
Input
n: il numero da classificare.
Output
Restituisci la stringa "abundant", "perfect" oppure "deficient", in minuscolo. 1 non ha divisori propri (somma 0), quindi è difettivo.
Vincoli
1 ≤ n ≤ 10^12
Esempi
Input:
n = 28
Output atteso:
expected = "perfect"
Input:
long long n = 28;
Output atteso:
std::string expected = "perfect";
Input:
long n = 28;
Output atteso:
string expected = "perfect";
Spiegazione
I divisori propri 1 + 2 + 4 + 7 + 14 danno come somma 28, quindi la risposta è "perfect".
Input:
n = 15
Output atteso:
expected = "deficient"
Input:
long long n = 15;
Output atteso:
std::string expected = "deficient";
Input:
long n = 15;
Output atteso:
string expected = "deficient";
Spiegazione
I divisori propri 1 + 3 + 5 danno come somma 9, che è minore di 15, quindi la risposta è "deficient".
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Se d divide n, anche n / d lo divide; fai girare d solo finché d × d ≤ n.
Suggerimento 2
Quando d × d = n, somma d una volta sola, non due.
Suggerimento 3
Ricordati di escludere n stesso dalla somma e di gestire a parte n = 1.
Complessità attesa
tempo O(√n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.