Déterminer tous les diviseurs d'un entier

Nous avons vu une première méthode pour trouver les diviseurs d'un nombre qui consister a essayer tous les nombres jusqu'à la racine carrée. Cette méthode est un peu naïve et peut être améliorée grâce à la décomposition en facteurs premiers. En effet, tous les diviseurs d'un nombre auront comme facteurs premiers ceux du nombre avec des exposants inférieurs. Il suffit donc de déterminer tous les produits de ce type que l'on peut fabriquer.

Reprenons l'exemple \(792 = 2^3\times 3^2\times 11\) et écrivons sous forme d'arbre tous les nombres que l'on peut composer à partir des mêmes facteurs mais à des exposants différents :

On en déduit le nombre de diviseurs : c'est le nombre de terminaisons (feuilles) de cet arbre, à savoir \(4\times 3\times 2 = 24\)

Un algorithme facile à programmer en python permet de les obtenir à partir de 3 boucles imbriquées :

1
for i in range(4):
2
    for j in range(3):
3
        for k in range(2):
4
            print(2**i*3**j*11**k)

La réponse est

1,2,3,4,6,8,9,11,12,18,22,24,33,36,44,66,72,88,99,132,198,264,396,792

Nombre de diviseurs

La méthode exposée ci-dessus montre le lien entre décomposition en facteurs premiers et nombre de diviseurs : ce dernier est égal au produit des exposants augmentés de 1 dans la décomposition du nombre en facteurs premier.

Question

En utilisant cet algorithme, Déterminez les diviseurs de 132.

Indice

\(132 = 2^2\times 3\times 11\)

Indice

Il y a \(3\times 2\times 2=12\) diviseurs

Solution

Question

Combien 1158057 a t-il de diviseurs ?

Indice

\(1158057 = 3^4 \times 17 \times 29^2\)

Solution

Il y a \(5\times 2 \times 3 = 30\) diviseurs.