So I'm trying to solve the third problem of Project Euler in which you have to get the largest prime factor of a number. I'm trying this problem via freeCodeCamp. I pass all tests of 2, 3, 5, 7, 8 and 13195, but from 13195 and upwards I get a Potential infinite loop detected on line 12. Tests may fail if this is not changed. warning. The final test of 600851475143 gives the following warnings:
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.
and the horribly wrong answer of 104441.
What could I have done wrong, since my loops don't look like they would run infinitely syntax-wise? Am I missing something here?
Code I'm using:
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));
Thanks in advance for the help!
You can't do 600 billion loops. Let's assume each number took up only 1 bit of storage(thats not the reality), then that would come up to over 70 GB of data from just the first portion of your code alone.
Your method works in theory but is too inefficient to be practical for such large numbers.
2 hints for this problem:
-You need to find all the number's prime factors, when going from the bottom up, you will find the prime numbers before you find any multiple of it . Let's see the number 30 as an example.
You find 2 as a factor. Now you know 2x15 = 30.
You've reduced the problem, now you have a prime factor of the number and only need to find the prime factors of 15.
Any prime factor of 15 is also by extension a prime factor of 30. Now lets keep looking. 3 divides into 15 to give 5.
The same logic applies, you would find 3 before 9,12,15 etc. So you know this factor is definitely prime.
Now you have another prime found. You now know 2x3x5 = 30. So you can check 5 now, 4 doesn't divide so go to 5.
5 is equal to 5, you can't go any further. Therefore all the prime factors of the number have been found.
There is no way you would find 4,6,8,10,12 as a factor before 2 for any number. -- You will always find the prime number as a factor before its multiples -- All the multiples of a prime are not prime. And they themselves can be split into a product of prime numbers. 6 = 3x2. 8 = 2x2x2, 10 = 5x2, 12=3x2x2 etc. So while doing this method, you will only get prime numbers.
6 is a factor of 30. but 6 = 3x2. 2 and 3 are both prime. and are both smaller than 6 and therefore would be found before 6 itself.
Lets consider the number 40 now.
2x20 = 40. 3 doens't divide into 20. now you get to 4 and see a problem. 4 itself is not prime but is found as a factor of 20 and according to what I explained earlier should be prime.
I've left one oversight in this explanation, and that regards the powers of primes. 4 = 2x2 (2^2) 8=2x2x2 (2^3) 16 = 2x2x2x2 (2^4).
-Factors come in pairs, whenever you find a factor, you find a matching factor with it. You only need to check up to the square root of a number to find all its factors. If no factor of a number has been found upto its square root then theres no need to progress any further, that number is definitely prime.
Anyways hope this helps