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))