Hoy vamos a ver cómo obtener el máximo común divisor de dos números usando el lenguaje de programación Python.

Usaremos Python para escribir dos funciones que nos van a ayudar a calcular el MCD de dos números, una recursiva y otra usando el ciclo while.

Recuerda que el máximo común divisor de dos números es el entero máximo que puede dividir a dos números sin dejar residuo.

Por ejemplo, el máximo común divisor de 6 y 20 es 2, ya que no hay número mayor que pueda dividir a ambos números (ya que el 3 puede dividir al 6 pero no al 20).

Veamos cómo resolver este ejercicio de programación con Python a través del algoritmo de Euclides.

Máximo común divisor con ciclo while

Veamos el primer enfoque, y es calcular el mcd de dos enteros usando el ciclo while. Dentro del ciclo simplemente vamos intercambiando variables y asignando a b el resultado de obtener el residuo de dividir a entre b.

El ciclo termina cuando b sea cero. En código queda así:

def maximo_comun_divisor(a, b):
    temporal = 0
    while b != 0:
        temporal = b
        b = a % b
        a = temporal
    return a

Fíjate en que estamos usando una variable temporal para ir guardando ahí el valor de b, ya que luego vamos a intercambiarlo con a.

Usando recursión

Si queremos ver el enfoque recursivo para el MCD usando Python podemos lograrlo igualmente con funciones. El código queda incluso más simplificado, pero la condición sigue siendo la misma: se va a detener cuando b sea 0.

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

La recursividad ocurre en la línea 4, pues invocamos a la función dentro de sí misma pero ahora pasamos a b como a (intercambiando la variable) y pasamos a b como el residuo de dividir a entre b.

Poniendo todo junto

Hasta ahora te he mostrado estos métodos en Python. Puedes usar el que más te convenga. Para usarlos y probarlos podemos ver el siguiente código completo:

"""
    https://parzibyte.me/blog
"""


def maximo_comun_divisor(a, b):
    temporal = 0
    while b != 0:
        temporal = b
        b = a % b
        a = temporal
    return a


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


a = 20
b = 6
resultado = maximo_comun_divisor(a, b)
resultado_recursivo = maximo_comun_divisor_recursivo(a, b)
print(
    f"El Máximo común divisor de {a} y {b} es {resultado}. De manera recursiva, es {resultado_recursivo}")

El modo de uso de las funciones se encuentra en las líneas 21 hasta 26. Obviamente estos valores pueden venir de cualquier lugar, yo los he colocado en el código por simplicidad.

Te dejo con un enlace para explorar más sobre Python en mi blog.