Proyecto Euler problema 5: múltiplo más pequeño

Este problema introduce un concepto que todos hemos estudiado en matemáticas: el mínimo común múltiplo. El problema no está planteado así, sino que nos pregunta por el número más pequeño que puede dividirse por una serie de números dando como resto cero. Veamos el enunciado:

2520 es el número más pequeño que se puede dividir por cada uno de los números del 1 al 10 dando como resto 0. ¿Cuál es el número positivo más pequeño que se puede dividir con resto 0 por todos los número del 1 al 20?

Por favor, intenta participar del espíritu del proyecto, y utiliza nuestras soluciones sólo para compararlas con las tuyas.

Lo cierto es que este problema nos sorprendió, pues al hacer el algoritmo nos dimos cuenta de que, en este caso, el método de “fuerza bruta” no cumpliría el requisito de hacerse en menos de un minuto. Si eliges un número n=1, empiezas a dividirlo por los números de 1 a 20, y cuando no es divisible (con resto cero) coges un número n=n+1, vas a llevarte una sorpresa, pues no alcanza la solución tan rápido como parece (de hecho, no la alcanza antes del minuto de rigor).

Una vez nos pusimos a pensar un poco, lo resolvimos en un momento con una calculadora de las de mano, pues se trata de factorizar 20 números y coger los “comunes y no comunes de mayor exponente”: es curioso cómo la frase que estudias de pequeño para acordarte del mínimo común múltiplo sin tener ni idea de qué significa se te queda grabada para siempre.

Pero no se trata de hacerlo con una calculadora, así que aquí os presentamos una solución. Básicamente hemos creado una función que descompone en factores primos todos los números que se le pasen en una lista, coge la lista de todos los factores elevados al máximo exponente que haya resultado de factorizar cada número, y los multiplica para calcular el mínimo común múltiplo. La función se puede mejorar en eficiencia, aun así el problema de los 20 primeros enteros está resuelto en menos de un segundo, por lo que no nos molestamos en optimizar de momento (queremos hacer algunos problemas más difíciles, este problema en el momento de escribir estas líneas ya fue resuelto por un cuarto de millón de almas, queremos llegar a problemas resueltos por menos de 200000 personas pronto ;-)).

¿Tienes una solución interesante al problema? ¿Alguna duda sobre nuestra solución? ¡Escríbela en los comentarios!

(Visto 530 vecess, 1 visitas hoy)

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *