Tous les défis
Facile 0 résolus 0 % de réussite

Somme des diviseurs stricts

Additionner tous les diviseurs de n strictement inférieurs à n.

Ce que vous allez apprendre

  • Trouver les diviseurs par paires
  • Arrêter la boucle à la racine carrée
  • Éviter de compter deux fois la racine carrée quand c'est un diviseur

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

Exemple 1
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.

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.