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

Sum of Proper Divisors

Add up every divisor of n that is smaller than n.

Ce que vous allez apprendre

  • Find divisors in pairs
  • Stop the loop at the square root
  • Avoid counting a square root divisor twice

Problème

Afficher la traduction

The proper divisors of n are the positive divisors other than n itself. For 12 they are 1, 2, 3, 4 and 6. Their sum (sometimes called the aliquot sum) tells whether a number is perfect, abundant or deficient. Divisors come in pairs d and n / d, so you only need to try values of d up to the square root of n.

Implement sum_of_proper_divisors(n).

Input

n: A positive integer.

Output

Return the sum of all positive divisors of n that are less than n. For n = 1 there are none, so return 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, so 28 is a perfect number.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

If d divides n, then n / d divides n too.

Indice 2

Only try d up to the square root of n, adding both members of each pair.

Indice 3

Leave n itself out, and add the square root only once when n is a perfect square.

Complexité attendue

O(sqrt n) time, O(1) extra space

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.