Calcular el MCD y el MCM

En esta lección obtendrás el máximo común divisor y el mínimo común múltiplo de dos números.

En Ruby no hay que programarlos: son métodos de los propios enteros. 12.gcd(18) da el máximo común divisor y 4.lcm(6) el mínimo común múltiplo.

El código de ejemplo muestra ambos.

Que sean métodos de un número, y no funciones sueltas, es coherente con la idea de que en Ruby todo es un objeto. También existe gcdlcm, que devuelve los dos de una vez en un array.

Por dentro usan el algoritmo de Euclides, que se basa en una observación de hace más de dos mil años: el MCD de dos números es el mismo que el del menor y el resto de dividirlos. Merece la pena implementarlo alguna vez como ejercicio de recursión —son tres líneas— aunque en código real siempre uses el método que ya viene hecho.

Donde aparecen de verdad es al simplificar fracciones, al sincronizar tareas con periodos distintos y en criptografía, donde el MCD es una pieza básica del cálculo de claves RSA.