Struggling with finding the correct prime factor for the final test case - Project Euler #3

JavaScript
1

Hey guys, I need some help here with solving 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 itself. I pass all tests of 2, 3, 5, 7, 8 and 13195, but 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 I don’t see any outright problems? Am I missing something here?

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(600851475143));

Thanks in advance for the help!

2

Issue here is probably efficiency. Original Project Euler problems usually require quite efficient way of solving challenge. Because tests on page have time limit, the efficiency requirements for some problems can be slightly more strict than, ie. if it would be solved locally.

Having said that, I believe sieve algorithm should work here for getting relevant primes, however version of it implemented in code doesn’t have yet some important optimizations that are present in classic sieve of Eratosthenes algorithm.

1 Like
3

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.