Per il calcolo del Massimo Comune Divisore puoi usare math.gcd(), Greatest Common Divisor
import math # gcd()
MCD = math.gcd(70, 15) # 5
Algoritmo di Euclide
L’algoritmo di Euclide permette di calcolare facilmente il massimo comun divisore.
MCD(a, b) è uguale a MCD(b, R), con R il resto della divisione intera tra a e b.
Quando b (il secondo argomento) diventerà zero il risultato sarà il valore di a.
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 | | |
+----+----+---+----+
a = 70
b = 15
while(b != 0):
resto = a % b
a = b
b = resto
print(a) # 5
Funzioni
Segue la tabella precedente
def mcd(a, b):
while(b != 0):
resto = a % b
a = b
b = resto
return a
print(mcd(70, 15)) # 5
Più corto…
def mcd(a, b):
while(b != 0):
a, b = b, a % b
return a
Versione ricorsiva
def mcd(a, b):
if(b == 0):
return a
else:
return mcd(b, a % b)