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):
f = factor(nombre)
while True:
for n in f:
if isPrime(n):
L = ['1']+factor(nombre)
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)
a=24769492052181606629
t=time()
print( liste_diviseurs(a) )
t=time()-t
print('temps :',t)
[1, 310547, 847193, 94147199, 263093244571, 29237130207853, 79760847962407, 24769492052181606629]
temps : 0.00298309326171875Voyez 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à…
