Máximo Común Divisor

En esta entrada vamos a ver un sencillo algoritmo para el cálculo del máximo común divisor de dos números dados. Recordemos que el máximo común divisor de dos números enteros positivos a y b, escrito como MCD(a, b), es el mayor de los divisores comunes de a y de b, es decir, el mayor de aquellos números que dividen a la vez a ambos. Por ejemplo MCD(6, 4) = 2, MCD(9, 6) = 3, y MCD(11, 9) = 1. El cálculo del máximo común divisor resulta muy útil a la hora de simplificar facciones, por ejemplo la fracción 60/18 podríamos simplificarla como 60/18 = (6*10) / (6*3) = 10 / 3.

En el siguiente algoritmo podemos encontrar un método para el cálculo del máximo común divisor. El algoritmo recibe como parámetros de entrada dos números, a y b, y como resultado nos muestra en pantalla el MCD(a, b). Para ello, el algoritmo se basa en un procedimiento muy simple: primero calcula cual es el menor de los números a y b, a continuación recorre todos los números que van desde 1 hasta el menor de a y b, y para cada uno de ellos comprueba si divide a la vez a ambos, utilizando la ya conocida función módulo(), que recordemos nos devuelve el resto de la división entera entre dos números x e y. Al final del bucle repetir, tendremos en la variable mcd el mayor de los números que han dividido a la vez a a y b, es decir, su máximo común divisor.

leer(a)
leer(b)
min := mínimo(a, b);
repetir desde x := 1 hasta x := min
    si (módulo(a, x) = 0) y 
           (módulo(b, x) = 0) entonces
        mcd := x
    fin si
fin repetir
escribir(mcd)

Existen muchas formas de mejorar el algoritmo anterior. Por ejemplo, no haría falta comprobar cuales son los divisores de a y b desde 1 hasta mínimo de a y b, bastaría con comprobar desde 1 hasta la raiz cuadrada del mínimo (¿podría explicar el lector por qué?). Otra manera más refinada de calcular el MCD sería mediante la factorización de los números a y b, aunque este procedimiento no es necesariamente más eficiente.

En la siguiente entrada de este blog veremos una forma muy sencilla, y muy eficiente, de calcular el máximo común divisor de dos números, el conocido como Algoritmo de Euclides.