Problème
Les diviseurs stricts (ou diviseurs propres) de n sont ses diviseurs positifs autres que n lui-même. Pour 12, ce sont 1, 2, 3, 4 et 6. Leur somme, parfois appelée somme aliquote, permet de savoir si un nombre est parfait, abondant ou déficient. Les diviseurs vont par paires d et n / d : il suffit donc de tester les valeurs de d jusqu'à la racine carrée de n.
Implémentez sum_of_proper_divisors(n).
Entrée
n : un entier strictement positif.
Sortie
Renvoyez la somme de tous les diviseurs positifs de n strictement inférieurs à n. Pour n = 1, il n'y en a aucun : renvoyez 0.
Contraintes
1 ≤ n ≤ 10^12
Exemples
Entrée :
n = 12
Sortie attendue :
expected = 16
Entrée :
long long n = 12;
Sortie attendue :
long long expected = 16;
Entrée :
long n = 12;
Sortie attendue :
long expected = 16;
Explication
1 + 2 + 3 + 4 + 6 = 16.
Entrée :
n = 28
Sortie attendue :
expected = 28
Entrée :
long long n = 28;
Sortie attendue :
long long expected = 28;
Entrée :
long n = 28;
Sortie attendue :
long expected = 28;
Explication
1 + 2 + 4 + 7 + 14 = 28, donc 28 est un nombre parfait.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Si d divise n, alors n / d divise aussi n.
Indice 2
Ne testez d que jusqu'à la racine carrée de n, en ajoutant les deux membres de chaque paire.
Indice 3
Laissez n de côté, et n'ajoutez la racine carrée qu'une seule fois lorsque n est un carré parfait.
Complexité attendue
temps O(sqrt n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.