Máximo Común Divisor

Descripción

El Máximo Común Divisor (MCD) de dos números, a y b, es el número más grande que divide exactamente (sin residuo) a ambos números.

Una forma de encontrar el MCD de dos números se basa en la observación de que si r es el residuo de la división de a entre b, entonces mcd(a, b) == mcd(b, r). Como caso base de una función recursiva que implemente esta solución se puede usar mcd(a, 0) == a

Escribe una función llamada mcd que tome parámetros a y b y devuelva el Máximo Común Divisor.

Ejemplo de Ejecución:

Este es el resultado al ejecutar la función con los siguientes argumentos

mcd(75, 15)
15

mcd(20, 100)
20

mcd(963, 27)
9

Solución

def mcd(a, b):
  if b == 0:
      return a
  else:
      return mcd(b, a % b)

print(mcd(75, 15))
print(mcd(20, 100))
print(mcd(963, 27))

Fuente del ejercicio: https://allendowney.github.io/ThinkPython/chap06.html#id3