Liste des diviseurs d’un nombre avec Python

Obtenir la liste de tous les diviseurs d’un nombre en Python peut se faire de plusieurs façons. Nous allons en voir quelques unes ici.

Obtenir la liste des diviseurs d’un nombre avec Python: la manière brutale

C’est la manière la plus répandue et aussi la plus simple, il suffit de faire une boucle de 1 jusqu’au nombre et de tester la divisibilité de chacun des nombres rencontrés.

def liste_diviseurs( n ):
    L = [1]
    for i in range(2,n+1):
        if n%i == 0:
            L.append(i)
            
    return L

>>> liste_diviseurs( 198 )
[1, 2, 3, 6, 9, 11, 18, 22, 33, 66, 99, 198]

C’est vrai que c’est simple et rapide! Enfin… Essayez avec ceci:

>>> liste_diviseurs( 1985856585 )

Vous allez vous en mordre les doigts… 🙂

La complexité de cette fonction est en O(n). Autant dire que plus le nombre n est grand, plus long sera le temps d’exécution.

Obtenir la liste des diviseurs d’un nombre avec Python à l’aide de la décomposition en produit de facteurs premiers

Une deuxième approche est d’utiliser la décomposition en produit de facteurs premiers du nombre. Alors, certes, l’implémentation est moins directe que la précédente, mais elle a son avantage…

J’ai déjà parlé dans cet article d’une manière d’obtenir la décomposition en produit de facteurs premiers.

from itertools import combinations

def decomp(n):
    D = dict() # dictionnaire vide
    k = 2
    while n > 1:
        exposant = 0
        while n%k == 0:
            exposant += 1
            n /= k
        if exposant != 0:
            D[k] = exposant
        k = k + 1
        
    return D

def liste_diviseurs(nombre):
    D = decomp(nombre)
    L = ['1']
    for key,value in D.items():
        for _ in range(value):
            L.append(str(key))
            
    A = [ [] for _ in range(len(L)-1) ]
    
    for i in range( 2 , len(L)+1 ):
        for j in combinations(L,i):
            if j not in A[i-2]:
                A[i-2].append( j )
        
    diviseurs_list = [1]
    for line in A:
        for c in line:
            p = 1
            for n in c:
                p *= int(n)
            if p not in diviseurs_list:
                diviseurs_list.append(p)
    
    return sorted(diviseurs_list)

L’avantage de cette façon de faire est que l’on réduit considérablement le nombres d’opérations.

Quand le programme précédent met énormément de temps à afficher le résultat (d’ailleurs, sur mon ordinateur Processeur Intel 12th Gen. Core i7-2.3 Ghz, 16 Go RAM), après 20 secondes, il n’y a rien qui s’affiche), ce dernier met 11 secondes. C’est mieux, mais pas ouf non plus…

Nous allons voir qu’il existe une manière bien plus rapide!

Accélération

Il faut accélérer la manière dont on décompose en produit de facteurs premiers le nombre. Je me suis donc mis à la recherche d’un script performant et je suis tombé sur la page https://www.codingame.com/playgrounds/53943/decomposition-en-facteurs-premiers-. Cela m’a permis d’améliorer le code précédent pour le suivant:

from time import time
from random import randint
from itertools import combinations

# Origine du code suivant: https://www.codingame.com/playgrounds/53943/decomposition-en-facteurs-premiers-

def gcd(a,b):
    # Calcule le PGCD de a et b
    while b>0:
        a,b=b,a%b      
    return a

def millerTest(a,d,n,r):
    # test de Miller pour un témoin a
    # Retourne faux si n est composé et vrai si n est probablement premier
    # d et r doivent vérifier n = 2^r * d + 1 avec d impair   
           
    x = pow(a, d, n) # Calcule a^d % n   
    if (x == 1  or x == n-1): 
       return True

    for _ in range(r):    
        x = (x * x) % n 
        if (x == 1):
            return False 
        if (x == n-1):
            return True    
   
    return False 

def isPrime(n, k=25): 
    # Test de primalité de Miller Rabin  
    # Si faux alors n est composé et si vrai alors n est probablement premier 
    # k determine le niveau de certitude : P(erreur) < 1/4**k
    
    if (n <= 1 or n == 4):
        return False 
    if (n <= 5):
        return True   
    
    # Trouver d et r tels que n = 2^r * d + 1 avec d impair 
    d = n - 1 
    r = 0
    while (d&1 == 0): 
        d  >>= 1 
        r += 1 
    
    # Effectuer k tests de Miller
    for i in range(k):
        a = randint(2,n-2) 
        if (not millerTest(a, d, n, r)):
              return False  
    return True

def nextPrime(n):
    # premier suivant n
    while not isPrime(n):
        n += 1
    return n

def pollard(n,a=1,c=3):
    # Recherche un diviseur de n
    # Cet algorithme est un mélange des méthodes rho et p-1 de Pollard
    # Echec,si la valeur retournée est n 
    if n&1==0: #pair
        return 2
    b,g=a,1   
    while g==1:
        a = (a*a+1)%n
        b = (b*b+1)%n
        b = (b*b+1)%n
        c = pow(c,a,n)
        g = gcd(n, ((c-1)*abs(b-a))%n)
    
    #print('Polard rho et p-1 : iter', i, 'n=', n,'g=', g)
    return g

def rho(n,a=2):
    # Recherche un diviseur de n
    # Cet algorithme est une variante de la méthodes rho de Pollard
    # Echec,si la valeur retournée est n   
    x=a  
    g=k=p=1
    i=0    
    while g==1:
        a = (a*a+1)%n
        f = abs(a-x)
        if f==0 or i%k==0:
            g = gcd(n,p)
            if f==0:
                break
            k<<=1
            x = a
            p = 1
               
        i += 1
        p *= f
        p %= n
        if p==0 and g==1:
            g = gcd(f,n)
                
    #print('Rho : iter', i, 'n=', n, 'g=', g)
    return g

def factor(n, k=25, div=rho):
    # Décompose n en facteurs probablement premiers
    # div = pollard ou rho
    comp = pow(2,n,n)!=2 # n est composé si vrai
    if n==2 or (n<341 and not comp): # n est un premier < 341 
            return [n]
    if not comp and isPrime(n,k): # n est probablement premier
        return [n]
    if n&1==0: # n est pair
        return [2]+factor(n>>1)
    for p in [3,5,7,11,13,17,19]:
        if n%p==0: #n est divisible par un petit premier
            return [p]+factor(n//p)
    f=div(n) # f est un facteur de n   
    while f==1 or f==n: # tant qu'on n'a pas de facteur strict
        # on essaye avec d'autres valeurs
        f=div(n,a=randint(0,n-1))                   
    return factor(f)+factor(n//f)

# fin du code

def liste_diviseurs(nombre):
    facteurs = factor(nombre)

    # Regroupement des facteurs premiers
    puissances = {}

    for p in facteurs:
        puissances[p] = puissances.get(p, 0) + 1

    diviseurs = [1]

    for p, exposant in puissances.items():
        nouveaux = []

        for d in diviseurs:
            puissance = 1

            for _ in range(exposant):
                puissance *= p
                nouveaux.append(d * puissance)

        diviseurs += nouveaux

    return sorted(diviseurs)

a=24769492052181606629
t=time()
        
print( liste_diviseurs(a) )

t=time()-t
print('temps :',t) 

[1, 310547, 847193, 94147199, 263093244571, 29237130207853, 79760847962407, 24769492052181606629]
temps : 0.00298309326171875

Voyez la différence de temps d’exécution!

Nous devons donc retenir de ceci le fait suivant: un programme court n’est pas toujours le meilleur programme, ni même le plus performant, loin de là…

Avec le module sympy

from sympy import divisors
from time import time

n = 24769492052181606629
t=time()
liste = divisors(n)
t=time()-t
    
print("Les diviseurs de {} sont : {} (trouvée en {} secondes)".format(n, liste, t ))

Les diviseurs de 24769492052181606629 sont : [1, 310547, 847193, 94147199, 263093244571, 29237130207853, 79760847962407, 24769492052181606629] (trouvée en 0.004564046859741211 secondes)