Nombre de diviseurs avec factorisation en nombres premiers
Une approche naïve pour déterminer le nombre de multiples d’un entier positif
n consiste à parcourir toutes les valeurs de 1 à n inclus et à compter combien d’entre elles divisent effectivement n.Cependant, cette méthode est très lente. Il est possible de calculer le nombre de diviseurs de
n en utilisant ses facteurs premiers (la recherche de ces facteurs ne nécessite qu’un temps de l’ordre de ).Imaginons que l’on représente un nombre comme le produit de ses facteurs premiers :
On peut déterminer le nombre de diviseurs de
n en prenant tous les exposants de sa factorisation, en leur ajoutant 1, puis en multipliant ces valeurs entre elles :Cela peut s’implémenter de manière similaire à la recherche des facteurs premiers de
n :n = ...
p, divisors = 1, 1 # facteur premier et le nombre de diviseurs
while p * p <= n: # tant que p <= sqrt(n)
p += 1 # Ajouter 1 au facteur premier à chaque itération
if n % p != 0: # Ne rien faire si n n'est pas divisible par p
continue
exp = 0 # compteur pour l'exposant
while n % p == 0: # diviser autant de fois que possible
n //= p
exp += 1
divisors *= exp + 1 # mettre à jour le produit
if n > 1: # si p > sqrt(n) => n est lui-même un facteur premier
divisors *= 2 # ajouter n en tant que diviseur avec un exposant 1
print(divisors)Défi : Trouver le nombre de diviseurs de n
On vous donne un entier
n. Vous devez trouver le nombre total de diviseurs de n.Entrée
La première ligne de l’entrée contient un seul entier
n (2 ≤ n ≤ ).Sortie
Le programme doit afficher le nombre de diviseurs de
n.Exemples
Input | Output |
8 | 4 |
17 | 2 |
2048 | 12 |
48 | 10 |
Bonus : Pourquoi l’ajout de 1 à chacun des exposants, puis la multiplication de ces valeurs, donne-t-il le nombre total de diviseurs de n ?
L’idée derrière cette formule est de considérer que le nombre de diviseurs correspond aux différentes combinaisons possibles de facteurs premiers. L’exposant de chaque facteur représente le nombre de fois où il peut intervenir dans la composition d’un diviseur de
n. En ajoutant 1 à chaque exposant, on inclut aussi la possibilité de ne pas utiliser ce facteur (ce qui correspond notamment à n lui-même et à 1 en tant que diviseurs). Enfin, le fait de multiplier ensemble tous les (« exposant + 1 ») de chaque facteur tient compte de toutes les combinaisons et donne le nombre total de diviseurs de n.Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB