Calculer le PPCM de plusieurs nombres avec Python peut paraître simple au premier abord, mais tout dépend du cahier des charges…
Calcul du PPCM avec Python: cahier des charges
Il existe une relation mathématique intéressante:$$\text{ppcm}(a,b)\times\text{pgcd}(a,b)=ab.$$
Le calcul du PGCD étant simple (avec l’algorithme d’Euclide par exemple), il serait aisé de se servir d’une fonction retournant le PGCD pour en déduire le PPCM.
Mais je ne souhaite pas faire appel au PGCD (ici, je ne chercherai donc pas à optimiser mon code Python). Je me fiche de la complexité algorithmique de mon programme: je cherche une approche naïve.
Trois fonctions
Pour calculer le PPCM de plusieurs nombres, je vais avoir besoin de trois fonctions.
Une fonction qui décompose en produit de facteurs premiers mon nombre
def decomp(n):
L = dict()
k = 2
while n != 1:
exp = 0
while n % k == 0:
n = n // k
exp += 1
if exp != 0:
L[k] = exp
k = k + 1
return LCette fonction retourne un dictionnaire Python contenant tous les facteurs premiers de l’argument n, qui vont être les clés du dictionnaire. La valeur des clés sera l’exposant de la clé, donc du facteur. Par exemple:
>>> decomp(60)
{2: 2, 3: 1, 5: 1}signifie que:$$60=2^2\times3^1\times5^1.$$
Une fonction qui calcule le PPCM de deux nombres entiers
def _ppcm(a,b):
Da = decomp(a)
Db = decomp(b)
p = 1
for facteur , exposant in Da.items():
if facteur in Db:
exp = max(exposant , Db[facteur])
else:
exp = exposant
p *= facteur**exp
for facteur , exposant in Db.items():
if facteur not in Da:
p *= facteur**exposant
return pL’idée ici est de construire deux dictionnaires Da et Db des facteurs premiers des nombres a et b.
Ensuite, on parcourt le dictionnaire Da et pour chacune des clés, on regarde si elle est dans Db: si tel est le cas, on prend l’exposant le plus élevé, sinon on prend l’exposant de la clé dans Da. On a préalablement initialisé une variable p qui va contenir le produit des facteurs premiers élevés aux exposants les plus élevés. À chaque facteur rencontré, on multiplie la valeur de p par le facteur élevé à l’exposant maximal.
Une fois Da parcouru, on parcourt Db en ne prenant que les facteurs qui ne sont pas dans Da, avec leur exposant, pour “compléter” p.
La valeur retournée est le PPCM de a et b.
La fonction retournant le ppcm de plus de deux nombres
def ppcm(*args):
L = list( args )
while len( L ) > 1:
a = L[-1]
L.pop()
b = L[-1]
L.pop()
L.append( _ppcm(a,b) )
return L[0]L’idée ici est de créer une liste L à partir du tuple mis en argument, puis de la parcourir tant que sa longueur est plus grande que 1.
On prend le dernier et l’avant-dernier élément, et on calcule leur PPCM. On les supprime et on ajoute à la fin le PPCM calculé.
Au final, la liste contiendra une unique valeur: le PPCM de tous les nombres initiaux.
>>> ppcm(12,8,42)
168Optimisation du calcul du PPCM de plusieurs nombres en Python
Les plus “pythonesques” d’entre vous auront vu immédiatement que cette façon de voir les choses n’est pas du tout optimale… mais je vous ai prévenu dès le début 🙂
Par exemple, dans la troisième partie, on pourrait “diviser pour régner“, c’est-à-dire calculer le PPCM de 2 en 2 dans la liste L.
def ppcm(*args):
L = list( args )
if len(L) == 2:
return _ppcm(L[0],L[1])
else:
n = len(L)
i = 0
A = []
while i <= n-2:
A.append( _ppcm( L[i] , L[i+1] ) )
i += 2
if n % 2 != 0:
A.append( L[n-1] )
return ppcm( *A ) Il faut faire attention à la manière dont on passe un tuple en argument d’une fonction comme la nôtre. J’ai trouvé l’astuce consistant à mettre “*A” au lieu de “A” en argument sur le topic https://stackoverflow.com/questions/46794115/passing-a-tuple-in-args.
Pour les PGCD et PPCM, j’ai ça :
def combinations(liste): n=len(liste) for i in range(2**n): b=[int(j) for j in bin(i)[2:].rjust(n,"0")] yield [liste[j] for j in range(n) if b[j]] def pgcd(*args): if len(args)==0: return 1 a=args[0] d=a for b in args[1:]: while b: d=b a,c=divmod(a,b) a,b=b,c return d def ppcm(*args): n=len(args) p=1 q=1 for l in combinations(args): if len(l)%2: p*=pgcd(*l) else: q*=pgcd(*l) return p//qPour le PGCD, j’utilise l’algorithme d’Euclide. Pour le PPCM, une formule similaire à la formule de Poincaré.