Así que estoy tratando de resolver el tercer problema del Proyecto Euler en el que tienes que obtener el factor primo más grande de un número. Estoy intentando este problema a través de freeCodeCamp . Paso todas las pruebas de 2, 3, 5, 7, 8 y 13195, pero desde 13195 y hacia arriba obtengo un Potential infinite loop detected on line 12. Tests may fail if this is not changed. advertencia. La prueba final de 600851475143 da las siguientes advertencias:
Potential infinite loop detected on line 6. Tests may fail if this is not changed. Potential infinite loop detected on line 15. Tests may fail if this is not changed. Potential infinite loop detected on line 12. Tests may fail if this is not changed.y la respuesta terriblemente incorrecta de 104441.
¿Qué podría haber hecho mal, ya que mis bucles no parecen ejecutarse infinitamente en cuanto a la sintaxis? ¿Me estoy perdiendo de algo?
Código que estoy usando:
const eratoSieve = (n) => { let primes = [2, 3, 5, 7]; if (n > 7) { primes = []; for (let i = 2; i <= Math.sqrt(n); i++) { primes.push(i); } } for (let j = 0; j < primes.length; j++) { let currentMultiple = primes[j]; for (let k = j + 1; k < primes.length; k++) { if (primes[k] % currentMultiple === 0) { primes[k] = false; } } } primes = primes.filter(elem => elem != false); return primes; }; function largestPrimeFactor(number) { let primeNums = eratoSieve(number); console.log(primeNums); let biggestPrime = 0; primeNums.forEach(elem => { (number % elem === 0) ? biggestPrime = elem : 0; }); return biggestPrime; } console.log(largestPrimeFactor(13195));¡Gracias de antemano por la ayuda!
No puedes hacer 600 mil millones de bucles. Supongamos que cada número ocupó solo 1 bit de almacenamiento (esa no es la realidad), entonces llegaría a más de 70 GB de datos solo de la primera parte de su código.
Su método funciona en teoría, pero es demasiado ineficiente para ser práctico para números tan grandes.
2 consejos para este problema:
-Necesitas encontrar todos los factores primos del número, al ir de abajo hacia arriba, encontrarás los números primos antes de encontrar cualquier múltiplo de él. Veamos el número 30 como ejemplo.
Encuentras 2 como factor. Ahora sabes 2x15 = 30.
Has reducido el problema, ahora tienes un factor primo del número y solo necesitas encontrar los factores primos de 15.
Cualquier factor primo de 15 también es por extensión un factor primo de 30. Ahora sigamos buscando. 3 se divide en 15 para dar 5.
Se aplica la misma lógica, encontrarías 3 antes de 9, 12, 15, etc. Así que sabes que este factor es definitivamente primo.
Ahora tienes otro primo encontrado. Ahora sabes que 2x3x5 = 30. Entonces puedes verificar 5 ahora, 4 no divide, así que ve a 5.
5 es igual a 5, no puedes ir más lejos. Por lo tanto, se han encontrado todos los factores primos del número.
No hay manera de encontrar 4,6,8,10,12 como factor antes de 2 para cualquier número. -- Siempre encontrarás el número primo como factor antes de sus múltiplos -- No todos los múltiplos de un primo son primos. Y ellos mismos se pueden dividir en un producto de números primos. 6 = 3x2. 8 = 2x2x2, 10 = 5x2, 12 = 3x2x2, etc. Entonces, al hacer este método, solo obtendrás números primos.
6 es un factor de 30. pero 6 = 3x2. 2 y 3 son ambos primos. y son ambos más pequeños que 6 y, por lo tanto, se encontrarían antes que 6.
Consideremos ahora el número 40.
2x20 = 40. 3 no se divide en 20. Ahora llegas a 4 y ves un problema. 4 en sí mismo no es primo pero se encuentra como un factor de 20 y de acuerdo a lo que expliqué antes debería ser primo.
He dejado un descuido en esta explicación, y eso se refiere a los poderes de los números primos. 4 = 2x2 (2^2) 8=2x2x2 (2^3) 16 = 2x2x2x2 (2^4).
-Los factores vienen en pares, cada vez que encuentras un factor, encuentras un factor coincidente con él. Solo necesita verificar hasta la raíz cuadrada de un número para encontrar todos sus factores. Si no se ha encontrado ningún factor de un número hasta su raíz cuadrada, entonces no hay necesidad de avanzar más, ese número es definitivamente primo.
De todos modos espero que esto ayude