Da Python 3.5 puoi usare math.gcd()
import math # gcd()
MCD = math.gcd(70, 15) # 5
Algoritmo di Euclide
L’algoritmo di Euclide permette di calcolare facilmente il massimo comun divisore.
Esempio: a=70, b=15, MCD(70, 15)=5
a b Q R
+----+----+---+----+
| 70 | 15 | 4 | 10 |
| 15 | 10 | 1 | 5 |
| 10 | 5 | 2 | 0 |
| 5 | 0 | | |
+----+----+---+----+
Versione iterativa: segue la tabella precedente
def euclide(a, b):
while(b != 0):
R=a%b
a=b
b=R
return a
print(euclide(70, 15)) # 5
Più corto…
def euclide(a, b):
while(b != 0):
a, b = b, a%b
return a
Versione ricorsiva
def euclide(a, b):
if(b == 0):
return a
else:
return euclide(b, a%b)
Minimo Comune Multiplo
Il minimo comune multiplo può essere calcolato facilmente utilizzando il Massimo Comune Divisore:
a = 70
b = 15
MCD = euclide(a, b) # MCD=math.gcd(a,b)
mcm = a*b/MCD
print("MCD =", MCD) # 5
print("mcm =", mcm) # 210