Máximo común divisor y mínimo común múltiplo. Algoritmo de Euclides en C.

Publicado por Eduardo González Vaquero | 29/09/2014

Máximo común divisor: es el mayor número entero que divide a dos o más números enteros dejando una división exacta (su residuo o resto es 0).

Mínimo común múltiplo: es el número que es el menor múltiplo común de dos o más números.

¿Qué es el algoritmo de Euclides?

Es un proceso lógico por el cual, dados dos números enteros, se calcula su máximo común divisor. Llamemos a y b a esos dos números.

Calculamos el resto de la división entera a/b.
- Si el resto es 0, a es el mínimo común múltiplo.
- Si el resto no es 0, le damos a a ese valor. Repetimos el primer paso.

Esto tiene su base en que a y b tienen el mismo M.C.D. que b y el resto de a/b.

mcd(a,b) = mcd(b,(a%b));

a%b es el resto de la división a/b.

Implementación en C/C++ del algoritmo de Euclides. Función para el M.C.D.

int mcd(int a,int b) {
    if(b == 0) return a;
    else return mcd(b,a%b);
}

Calcular el mínimo común múltiplo.

Resultará del cocientre entre el producto de los números y el máximo común divisor de éstos.

int mcm(int a,int b) {
    return (a*b)/mcd(a,b);
}

Programación