Algorithme de calcul rapide du pgcd et ppcm
Par pepin le vendredi, octobre 18 2019, 23:56 - Python - Lien permanent
La décomposition en facteur premier est couteuse, même lorsqu'on à la liste des facteurs premiers en mémoire du programme. Il existe cependant des propriétés mathématiques permettant de calculer PGCD et PPCM sans passer par ces décompositions :
L'algorithme d'Euclide, et la propriété pgcd(a,b)*ppcm(a,b)=a*b
#!/usr/bin/env python3 def pgcd(a,b): while (b > 0): temp = b b = a % b a = temp return a def ppcm(a,b): return (int(a * (b / pgcd(a, b))))
Ceci fut trouvé dans le cadre d'un quizz hackerone et adapté en python.
A noter qu'il existe cet autre algorithme rapide de calcul du pgcd basé sur les propriété paires/impaires du pgcd : PCGD Binaire
Et comme je continue d'utiliser mes connaissances mathématiques, de l'associativité des PGCD et PPCM, on peut maintenant écrire :
def pgcg_array(a): p=a[0] for i in a[1:]: p=pgcd(p,i) return(p) def ppcm_array(a): p=a[0] for i in a[1:]: p=ppcm(p,i) return(p)
Enfin, dernière chose à dire d'un point de vue algorithmique. Comme notre calcul du ppcm dépend du calcul du pgdc; autant pour un calcule entre deux entiers, il n'y a rien d'important à changer. Mais quand nous travaillons sur un "array", les calculs sont fait plusieurs fois pour le pgcd. Il est préférable de fusionner le tout ...
def pgcd_ppcm_array(a): _pgcd=a[0] _ppcm=a[0] for i in a[1:]: _pgcd=pgcd(_pgcd,i) _ppcm=int((_ppcm*i)/_pgcd) # Renvoie des deux valeurs sous forme de liste return ((_pgcd,_ppcm))