- Calculamos el residuo de dividir el valor más grande de ambos sobre el más pequeño
- Si el resultado es 0, entonces el resultado es el numero más pequeño de los anteriores
- En caso contrario reemplazamos el numero mayor con el residuo y volvemos al paso 1
Una implementación sencilla en Java:
public static int MCD(int a, int b) {
if(b == 0)
return 0;
return MCD(a, a % b);
}
¡¡¡Si alguien me hubiese dicho esto en secundaria no hubiese sufrido tanto con esas cosas!!!
Otro tip. Para obtener el MCM de a y b, basta con multiplicar a * b y dividir entre el MCD.
La complejidad del algoritmo es del orden de O (log n)