Help with Project Euler Problem 3

[Agent67]

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. 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 - 1; k++)
    {
      if (primes[k] % currentMultiple === 0)
      {
        primes.splice(k, 1);
      }
    }
  }
  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!

 

[battletoad]

Not entirely sure why you have k < primes.length - 1 in that inner for-loop, since largestPrimeFactor(20) will return 4. Perhaps that's the reason you're getting 104441 back, however there's another sinister thing happening.

In this for-loop here, you're mutating the very thing you're looping on. This approach could also be the reason why 104441 appears in your sieve.

  for (let j = 0; j < primes.length; j++)
  {
    let currentMultiple = primes[j];
    for (let k = j + 1; k < primes.length - 1; k++)
    {
      if (primes[k] % currentMultiple === 0)
      {
        primes.splice(k, 1);
      }
    }
  }

Notice that you splice at index k, then increment k for your next iteration. Suppose you have the sequence ... n, n+1, n+2 ... at indices ... k, k+1, k+2, ... and furthermore suppose that n is divisible by currentMultiple.
What happens is that once you remove n from the array, n+1 is moved into index k and n+2 is moved into index k+1. But then you increment to k+1 for your next iteration, meaning you're skipping the divisibility check on n+1 (which is now at index k) and moving straight onto the check for n+2 (now at index k+1).

Coming back to 104441, it has prime factorisation 71 x 1471. If the sequence in the neighbourhood of 104441 is ..., (some number divisible by 71*, call it M), 104441, (other number), ..., then you'll remove M, skip by 104441 and move into (other number). Same applies for when 1471 comes around as currentMultiple. Maybe that's why 600851475143 was chosen in the first place :shrug:

For a quick win you could set the multiples as zero (simply to keep the length of the primes array constant during divisibility check), then return the array after filtering out those zeroes.

[edit] removed fast prime factorisation algos since they require a bit of machinery/understanding.

* Quick point here: remember your sieve would have removed quite a few numbers prior to getting to 71 (expectation being that 71 will remove 104441). So the number before 104441 may not be 10440 (actually - will not be, the prime 2 would've removed 10440 already).

 

[Agent67]

Not entirely sure why you have k < primes.length - 1 in that inner for-loop, since largestPrimeFactor(20) will return 4. Perhaps that's the reason you're getting 104441 back, however there's another sinister thing happening.

Ok, I repaired it. But still the same outcome with 600851475143.

For a quick win you could set the multiples as zero (simply to keep the length of the primes array constant during divisibility check), then return the array after filtering out those zeroes.

Ok, so I did do this in eratoSieve's function:

  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;

And still no progress with the 600851475143 number. It still returns 104441

 

[battletoad]

I PM'd you, have a look.

Just noticed another thing (not related to your 600851475143 issue), this condition on the for-loop:

for (let i = 2; i < Math.sqrt(n); i++)

the Math.sqrt(n) bit is a threshold used to find a divisor, but not necessarily the largest divisor. This means there'd be inputs to your program that would produce the wrong results.
e.g.

Number	Prime factors	Math.sqrt(n)	Your Program output
15	3, 5	3.872	3
77	7, 11	8.774	7

 

[Agent67]

I PM'd you, have a look.

Just noticed another thing (not related to your 600851475143 issue), this condition on the for-loop:

for (let i = 2; i < Math.sqrt(n); i++)

the Math.sqrt(n) bit is a threshold used to find a divisor, but not necessarily the largest divisor. This means there'd be inputs to your program that would produce the wrong results.
e.g.

Number	Prime factors	Math.sqrt(n)	Your Program output
15	3, 5	3.872	3
77	7, 11	8.774	7

Ohhhh ok, I see. Could it be possible to use recursion to fill the primes array then? (P.S I completely suck at recursion although I understand it theoretically, I never get how to implement it in practice)

 

[battletoad]

yeah you can use recursion for this. More on this later.

I don't see anything inherently wrong with your sieve code. Given the adjustments so far, it should be generating all the primes up to sqrt(whatever number you provided).

The thing about a sieve is that generating it is computationally heavy, as you've experienced thus far. Ideally, you'd generate a sieve, cache the results (forever, primes aren't changing anytime soon), then reuse when factoring's required later on. Your current code generates all the primes up to sqrt(number) for each run. But do you need all those primes in your sieve though? Are you able to minimise the number of primes before you get to that nested for-loop?

On recursion: recursion requires you to break the problem down so that the recursive calls terminate. In your case, problem = big number (i.e. do a literal substitution of problem = big number into previous sentence ).

I'd recommend you try to solve the problem with your current implementation, then circle back to attempt it via recursion. Thereafter you can compare both approaches.