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

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

Volver atrás

Publicado por |

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);
}



C/C++ algoritmosalgoritmiamatemáticas

Programación

Redes sociales

Twitter BrainumGoogle Plus BrainumFacebook Brainum


Política de privacidad