Proyecto Euler problema 3: mayor factor primo

En nuestro tercer problema del proyecto Euler debemos decir que la capacidad de cálculo de los ordenadores actuales (y del lenguaje python) nos ha sorprendido agradablemente. El problema nos presenta la búsqueda del mayor factor primo de un número concreto. Para ello tenemos que saber que es un factor primo, que no es más que un número que divide al número del enunciado y que además es primo. En realidad, todos los números se pueden descomponer en un conjunto de factores primos (este proceso se llama factorización). Veamos el texto del problema:

Los factores primos del número 13195 son 5,7,13 y 29. ¿Cuál es el factor primo mayor del número 600851475143?

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

Y ahí es donde nos ha sorprendido el resultado. ¿Véis ese número? En los tiempos mozos del que escribe había que hacer malabarismos para trabajar con números tan grandes. Hoy en día, el ordenador ni siquiera ha pestañeado. El algoritmo que presentamos tardó apenas un segundo en ejecutarse (a ojímetro).

Lo primero que hicimos al ver el enunciado fue a ponernos a investigar cómo calcular un montón de números primos. Al fin y al cabo, es lo que dice el problema, buscar el mayor factor primo. Pensábamos que trabajaríamos con números grandes y nos pusimos a buscar infinidad de métodos. Dejar que os diga una cosa: estamos verdes en matemáticas, calcular primos es bastante complicado.

Luego pensamos: si vamos a tener que dividir mucho mucho para calcular primos, vamos sencillamente a dividir por números que van incrementando, y si encontramos un número “divisor”, pues dividimos “número inicial” por “divisor” porque es un factor de éste. Nuestro “número siguiente” será ahora “número inicial/divisor”, pues estamos factorizando el número inicial. Además, si contamos que pasaremos primero por un primo que por sus múltiplos, no será necesario controlar si nuestro número es primo. Si es divisible, como es el primero que encontramos, es primo (¿por qué? Porque si no fuera primo significa que es múltiplo de un número inferior, por el que habríamos pasado).

Ejemplo: el 12195 lo dividimos por 2,3,4 sin éxito (no son divisores), por 5 es divisor, nos queda  2639 que será nuestro próximo número de trabajo. Lo dividimos por 5 y 6 (no son divisores) y por 7 que sí es divisor y nos queda 377. Ahora dividimos por 7,8,9,10,11,12 (no son divisores) y por 13, que sí es divisor y nos queda 29. Dividimos por 13,14,15,16,17… hasta 29, que es el último divisor. Como 29 es el mayor divisor que encontramos, pues es es mayor factor primo de 12195.

Sí, son un montón de divisiones innecesarias… pero es que para calcular primos se hacen también muchas y tendríamos que hacer tropecientas divisiones también. Total, que como dijimos el cálculo es sorprendentemente rápido, así que no vamos a complicarnos. Fuerza bruta y python ;-).

 

Edit: para uno de los retos de Hackerrank, hemos necesitado mejorar la función de cálculo del máximo divisor, pues nuestra solución no pasaba todos los casos. Mejoras introducidas: los números avanzan de dos en dos (pues sabemos que es impar una vez descartemos que es el dos), y el máximo divisor posible es la raíz del número original, pues si pasamos ese número sabemos que el número restante es primo (una de las propiedades de los primos es que sólo puede haber un factor primo mayor de raíz de N). Si pasamos ese divisor sabemos que el número que nos queda es primo.

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

(Visto 437 vecess, 1 visitas hoy)

Deja un comentario

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