Máximo común divisor (MCD) en Python

Esta entrada del blog pertenece a una serie:

• Números primos en Python
• Factorización en Python
• Máximo común divisor (MCD) en Python
• Mínimo común múltiplo (mcm) en Python

Veamos la denominación en inglés y en español.

• gcd = greatest common divisor = máximo común divisor = MCD
• lcm = least common multiple = mínimo común múltiplo = mcm

Código en repl.it

Concepto y resolución manual

El máximo común divisor de dos números x e y es el mayor número capaz de dividir a ambos de forma exacta.

Los divisores de 300 y de 33.880 son los siguientes.

• divisores(300) = 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300.
• divisores(33880) = 1, 2,4, 5, 7, 8, 10, 11, 14, 20, 22, 28, 35, 40, 44, 55, 56, 70, 77, 88, 110, 121, 140, 154, 220, 242, 280, 308, ...

Como se puede comprobar, viendo todos los divisores, el número 20 es el mayor de todos los divisores comunes de ambos. Si bien, no es necesario calcular todos los divisores de ambos números, existe otro procedimiento que consiste en efectuar la descomposición en factores primos de esos números.

Descomposición en factores primos:

• 300 = 2^2 × 3 × 5^2 × 1
• 33880 = 2^3 × 5 × 7 × 11^2 × 1

MCD → comunes a la mínima potencia = 2^2 × 5 = 20

Usos del máximo común divisor

Algunos de los usos del MCD son:

• Simplificar fracciones

• Para calcular el mcm (mínimo común múltiplo)

a × b = MCD(a,b) × mcm(a,b)

Método 1: con gcd

Podemos calcular el MCD (máximo común divisor) en Python usando la librería math con:

math.gcd

Ejemplo: calcular el máximo común divisor entre 300 y 33.880

from math import gcd  
x=300  
y=33880  
print("El máximo común divisor entre {} y {} es: ".format(x,y))  
print(gcd(x,y))  

Método2: buscando los divisores comunes

Dados dos números a y b vamos a dividir entre todos los números entre 1 y el menor de ambos buscando los números que proporcionan división exacta, y dentro de ellos aquellos que son comunes a ambos. Te todos los comunes el mayor de ellos será el máximo común divisor (MCD).

#!/bin/python3  
# MCD → Máximo común divisor  
def frac(a,b):  
  return (a/b) - int(a/b)  
def mcd(a,b):  
  maximo=1  
  for i in range(1,min(a,b)+1): #dividiendo entre todos los números anteriores al mínimo de los dos números a y b  
    # si al dividir ambos a y b entre i la división es exacta indicará que ese i es un divisor común a ambos  
    if frac(a,i)<1e-9 and frac(b,i)<1e-9: #ponemos <1e-9 y no ==0 para evitar posibles errores de redondeo al dividir dos números  
      maximo=i   #buscamos el máximo común divisor de ambos  
  return maximo      
x=300  
y=33880  
print("MCD({},{}) = {}".format(x,y,mcd(x,y)))  # MCD(300,33880) = 20  

Método 3: algoritmo de Euclides

Dados dos números a y b vamos a calcular el Máximo Común Divisor utilizando el algoritmo de Euclides. Los pasos son los siguientes:

1. Nos aseguramos que el número a sea el mayor de los dos
2. Calculamos el resto o módulo de dividir a entre b
3. Ahora el valor a será el antiguo b y b será el módulo anteriormente calculado
4. Se repite el proceso desde el paso 2, hasta que se llegue a conseguir que el módulo sea cero.
5. Cuando el módulo es cero, ya habremos conseguido el MCD que será el último valor de b obtenido en este proceso.

En la tabla anterior se puede ver el algoritmo en las columnas E y F. Las columnas G y H no son necesarias para el funcionamiento del algoritmo. En nuestro ejemplo se puede ver que el MCD entre 180 y 1032 es igual a 12.

En las columnas B y C se marcan en amarillo todos los divisores de 180 y de 1032. Los colores amarillos coinciden en 1, 2, 3, 4, 6 y 12. Luego no vuelven a coincidir. Como se pude ver 12 es el mayor de los divisores comunes a ambos números.

def MCD(a,b): # algoritmo de Euclides  
 if b>a:a,b=b,a #para que a sea el mayor  
 while a%b!=0:  
  b,a=a%b,b  
 return b  
x=180  
y=33880  
print('El MCD de {} y {} es {}.'.format(x,y,MCD(x,y)))