El problema con el Proyecto Euler es que normalmente hay un método obvio de fuerza bruta para hacer el problema, que tomará casi para siempre . A medida que las preguntas se vuelvan más difíciles, tendrás que aplicar soluciones inteligentes.
Una forma de resolver este problema es utilizar un bucle que encuentre siempre el factor más pequeño (entero positivo) de un número. Cuando el factor más pequeño de un número es ese número, ¡entonces has encontrado el mayor factor primo!
Descripción detallada del algoritmo:
Para ello, hay que mantener tres variables:
- El número que está tratando de factorizar (A)
- Un almacén divisor actual (B)
- Un almacén del mayor divisor (C)
Inicialmente, sea (A) el número que le interesa - en este caso, es 600851475143. A continuación, deja que (B) sea 2. Ten una condicional que compruebe si (A) es divisible por (B). Si es divisible, dividir (A) por (B), restablecer (B) a 2, y volver a comprobar si (A) es divisible por (B). En caso contrario, si (A) no es divisible por (B), se incrementa (B) en +1 y se comprueba si (A) es divisible por (B). Ejecuta el bucle hasta que (A) sea 1. El (3) que devuelva será el mayor divisor primo de 600851475143.
Hay numerosas formas de hacer esto más efectivo - en lugar de incrementar al siguiente entero, podrías incrementar al siguiente entero necesariamente primo, y en lugar de mantener un almacén de divisor mayor, podrías simplemente devolver el número actual cuando su único divisor es él mismo. Sin embargo, el algoritmo que he descrito anteriormente se ejecutará en segundos de todos modos.
Has dicho que no quieres una respuesta directa. De todos modos, si quieres ver una implementación de la misma, he subido mi código para este problema en Pastebin: aquí (C) y aquí (Python) .
Ejemplo: Vamos a encontrar el mayor factor primo de 105 utilizando el método descrito anteriormente.
Sea (A) = 105. (B) = 2 (siempre empezamos con 2), y aún no tenemos un valor para (C).
¿Es (A) divisible por (B)? No. Incrementa (B) en +1: (B) = 3. ¿Es (A) divisible por (B)? Sí. (105/3 = 35). El mayor divisor encontrado hasta ahora es 3. Sea (C) = 3. Actualiza (A) = 35 . Reinicio (B) = 2.
Ahora, ¿es (A) divisible por (B)? No. Incrementa (B) en +1: (B) = 3. ¿Es (A) divisible por (B)? No. Incrementa (B) en +1: (B) = 4. ¿Es (A) divisible por (B)? No. Incrementa (B) en +1: (B) = 5. ¿Es (A) divisible por (B)? Sí. (35/5 = 7). El mayor divisor que hemos encontrado anteriormente está almacenado en (C). (C) es actualmente 3. 5 es mayor que 3, así que actualizamos (C) = 5. Actualizamos (A)=7. Reiniciamos (B)=2.
Entonces repetimos el proceso para (A), pero seguiremos incrementando (B) hasta que (B)=(A), porque el 7 es primo y no tiene más divisores que él mismo y el 1. (Ya podríamos parar cuando (B)>((A)/2), ya que no se pueden tener divisores enteros mayores que la mitad de un número - ¡el menor divisor posible (que no sea el 1) de cualquier número es el 2!)
Así que en ese punto volvemos (A) = 7.
Intenta hacer algunos de estos a mano y te harás a la idea. O simplemente juega con el código que te he proporcionado. Inserta algunas sentencias de impresión, ve cómo itera a través de los números.
