Perfect Number

Q: Quelle est la complexité temporelle de la vérification d’un nombre parfait ?

La collecte des paires de diviseurs jusqu’à √n prend un temps de O(√n) et un espace de O(1) . Pour n = 10^8 , cela représente environ 10^4 étapes. Tester chaque candidat jusqu’à n / 2 est en O(n) , soit environ 5 × 10^7 étapes pour la même entrée.

Q: Combien y a-t-il de nombres parfaits inférieurs à 10^8 ?

Cinq : 6 , 28 , 496 , 8128 et 33550336 . Ils se raréfient rapidement. Le suivant, 8589869056 , ne tient même pas dans un entier de 32 bits.

Q: Existe-t-il des nombres parfaits impairs ?

Personne ne le sait. Tous les nombres parfaits découverts jusqu’à présent sont pairs. Les recherches ont exclu l’existence de nombres parfaits impairs inférieurs à 10^1500 , mais aucune preuve ne montre qu’ils ne peuvent pas exister. Ta fonction doit s’appuyer sur la définition, et non sur l’hypothèse que l’entrée est paire.

Q: Quelle est la différence entre les nombres parfaits, abondants et déficients ?

Compare la somme des diviseurs propres au nombre. Si elles sont égales, le nombre est parfait, comme 28 . Si la somme est supérieure, le nombre est abondant, comme 12 , dont les diviseurs totalisent 16 . Si elle est inférieure, le nombre est déficient, comme tout nombre premier, dont le seul diviseur propre est 1 .

DébutantMaths et simulation

+10

Un diviseur propre de n est un diviseur positif inférieur à n lui-même. Un nombre parfait est égal à la somme de ses diviseurs propres : 6 = 1 + 2 + 3. On te donne un entier positif n. Renvoie true si n est parfait et false sinon.

Fonction

isPerfect(n: integer) → boolean

ninteger: l’entier positif à tester
Renvoieboolean: vrai si n est égal à la somme de ses diviseurs propres, faux sinon

Contraintes

1 ≤ n ≤ 10⁸

Exemples

Entrée: n = 28
Sortie: true
Explication: Les diviseurs propres de 28 sont 1, 2, 4, 7 et 14. Leur somme est égale à 28, donc 28 est parfait.

Entrée: n = 12
Sortie: false
Explication: Les diviseurs propres de 12 sont 1, 2, 3, 4 et 6. Leur somme est égale à 16, ce qui dépasse 12.

Entrée: n = 1
Sortie: false
Explication: 1 n’a aucun diviseur propre, donc la somme est 0, et non 1.

+16 tests cachés à la soumission

Pour aller plus loin

Tout nombre parfait pair est de la forme 2^(p-1) × (2^p-1) où 2^p-1 est premier. Peux-tu lister tous les nombres parfaits inférieurs à 10^8 à l’aide de cette formule, sans tester chaque nombre ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La définition demande une somme de diviseurs, et la boucle évidente teste chaque candidat jusqu’à n / 2. Pour n = 10^8, cela représente 5 × 10^7 divisions. Les diviseurs vont par paires dont le produit est égal à n ; tu peux donc récupérer les deux membres de chaque paire en ne cherchant que jusqu’à √n, soit environ 10^4 étapes.

Ajouter chaque diviseur propre

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Suis la définition. Essaie tous les d en partant de 1 et, lorsque n % d == 0, ajoute d à un total cumulé. À la fin, compare le total à n. Pour 28, la boucle ajoute 1, 2, 4, 7 et 14, et 1 + 2 + 4 + 7 + 14 = 28.

Tu peux t’arrêter à n / 2. Un diviseur différent de n donne un quotient d’au moins 2, il n’est donc jamais supérieur à la moitié de n. Cette borne fonctionne aussi pour n = 1 : la boucle s’exécute zéro fois, le total reste égal à 0 et la réponse est false.

Diviser la plage par deux ne change pas la croissance. Pour n = 10^8, la boucle s’exécute encore 5 × 10^7 fois, et elle le fait pour chaque entrée de cette taille, qu’elle soit un diviseur ou non.

Algorithme

Définissez total sur 0.
Faites une boucle sur d de 1 à n / 2.
Si n % d == 0, ajoutez d à total.
Renvoyez si total == n.

def isPerfect(n):
    total = 0
    # No proper divisor of n is larger than n / 2.
    for d in range(1, n // 2 + 1):
        if n % d == 0:
            total += d
    return total == n

Collecter les paires de diviseurs jusqu’à la racine carrée

Intuition

Lorsque d divise n, n / d le divise aussi. Pour 28, les paires sont 1 × 28, 2 × 14 et 4 × 7. Dans chaque paire, l’un des membres est inférieur ou égal à √n, car deux nombres supérieurs à √n ont un produit supérieur à n. Ainsi, une recherche jusqu’à √n rencontre chaque paire une fois, et tu ajoutes les deux membres au fur et à mesure.

Deux membres demandent une attention particulière. La paire 1 × n inclut n lui-même, qui n’est pas un diviseur propre : commence le total à 1 et la recherche à 2. Ce point de départ ne convient pas à n = 1, dont l’unique diviseur est lui-même ; renvoie donc false dans ce cas en premier. Et lorsque n est un carré, la racine est associée à elle-même : pour 36, 6 × 6 doit ajouter 6 une seule fois, et non deux.

Écris la borne sous la forme d * d ≤ n, qui reste en nombres entiers. Pour n = 10^8, la boucle s’arrête à d = 10^4 ; elle s’exécute donc environ 10^4 fois au lieu de 5 × 10^7.

Algorithme

Si n == 1, renvoie false.
Définis total sur 1 et d sur 2.
Tant que d * d ≤ n : si d divise n, ajoute d, et ajoute aussi n / d s’il est différent de d.
Passe au d suivant.
Renvoie si total == n.

def isPerfect(n):
    if n == 1:
        return False
    total = 1  # 1 divides every n > 1; n itself does not count
    d = 2
    while d * d <= n:
        if n % d == 0:
            total += d
            partner = n // d
            if partner != d:  # a square root pairs with itself: add it once
                total += partner
        d += 1
    return total == n

Pièges et cas limites

L’astuce des paires est simple, et chacune de ses erreurs modifie la somme d’exactement un diviseur.

Compter n lui-même. La paire 1 × n ajoute n, et alors tous les nombres semblent avoir une somme supérieure à n. Commence le total à 1 et la recherche à 2.
Considérer 1 comme parfait. Si le total commence à 1, l’entrée 1 donne la comparaison 1 == 1. La somme de ses diviseurs propres est 0 ; traite donc ce cas avant la boucle.
Ajouter deux fois une racine carrée. Pour 16, les diviseurs propres sont 1, 2, 4 et 8, dont la somme est 15. Ajouter 4 deux fois donne 19.
S’arrêter à d * d < n. Cela ignore complètement la racine carrée, donc 4 n’est jamais compté dans 16.
Déduire la borne d’une racine carrée en virgule flottante. En simple précision, ou au-delà de 2^53 en double précision, la racine d’un carré parfait peut être arrondie à l’entier inférieur et faire manquer un diviseur. Le test d * d ≤ n reste dans les nombres entiers et n’a jamais ce problème.

Questions fréquentes4

Quelle est la complexité temporelle de la vérification d’un nombre parfait ?

La collecte des paires de diviseurs jusqu’à √n prend un temps de O(√n) et un espace de O(1). Pour n = 10^8, cela représente environ 10^4 étapes. Tester chaque candidat jusqu’à n / 2 est en O(n), soit environ 5 × 10^7 étapes pour la même entrée.

Combien y a-t-il de nombres parfaits inférieurs à 10^8 ?

Cinq : 6, 28, 496, 8128 et 33550336. Ils se raréfient rapidement. Le suivant, 8589869056, ne tient même pas dans un entier de 32 bits.

Existe-t-il des nombres parfaits impairs ?

Personne ne le sait. Tous les nombres parfaits découverts jusqu’à présent sont pairs. Les recherches ont exclu l’existence de nombres parfaits impairs inférieurs à 10^1500, mais aucune preuve ne montre qu’ils ne peuvent pas exister. Ta fonction doit s’appuyer sur la définition, et non sur l’hypothèse que l’entrée est paire.

Quelle est la différence entre les nombres parfaits, abondants et déficients ?

Compare la somme des diviseurs propres au nombre. Si elles sont égales, le nombre est parfait, comme 28. Si la somme est supérieure, le nombre est abondant, comme 12, dont les diviseurs totalisent 16. Si elle est inférieure, le nombre est déficient, comme tout nombre premier, dont le seul diviseur propre est 1.

Python

def isPerfect(n):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

n = 28

Attendu

true