pgcdppcm.py

Created on July 22, 2020

650 Bytes

Calcule le PGCD et le PPCM de nombres. Le PGCD fonctionne seul, le PPCM utilise une méthode d’exclusion-inclusion et donc des combinaisons (sans itertools).

def combinations(liste):
  n=len(liste)
  for i in range(2**n):
    b=[int(j) for j in bin(i)[2:]]
    b=[0]*(n-len(b))+b # rjust n'est pas disponible
    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//q

if __name__=="__main__":
  print("PGCD(150,180,240)=%d"%pgcd(150,180,240))
  print("PPCM(150,180,240)=%d"%ppcm(150,180,240))