Project Euler Problems 1 to 100 - Problem 3: Largest prime factor

Project Euler
1

Tell us what’s happening:

My code passes all tests, except the last one. The last test is “largestPrimeFactor(600851475143) should return 6857”.

It does seem to return the correct number: 6857, but when I run it with this number, it states:
“There is a potential infinite loop detected on line 13. Tests may fail if this is not changed.
6857”

However, I cannot see where the infinite loop is. Even when I run it with largestPrimeFactor(Infinity), it doesn’t get caught in an infinite loop, so I’m quite stumped!

Your code so far

function isPrime(number) {
  let prime = true;
  for (let i = 2; i<=Math.ceil(Math.sqrt(number)); i++) {
    if (number % i == 0 && number != 2) {
      prime = false;
    }
  }
  return prime;
}

function largestPrimeFactor(number) {
  let primeArray = [];
  for (let i=2; i<= number; i++) {
    if (isPrime(i)) { primeArray.unshift(i)};
  }
  for (let i=0; i< primeArray.length; i++) {
    if (number % primeArray[i] == 0) {
      return primeArray[i];
    }
  }
  return "No prime factor";
}
console.log(largestPrimeFactor(600851475143));

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:142.0) Gecko/20100101 Firefox/142.0

Challenge Information:

Project Euler Problems 1 to 100 - Problem 3: Largest prime factor

2

This is an inefficient approach to building a list of primes, which is why your code is struggling with large inputs.

3

To further explain Jeremy’s answer: That warning shows when a function takes an exceptionally long time to execute. Basically, there is a time limit on the tests to try to prevent you from accidentally crashing your browser.

1 Like
4

It is not actually an infinite loop but it struggles in this line of code:
for (let i = 2; i <= number; i++)

Which is iterating like 600+ billion times. You can make it more efficient. Here are some suggestions:

  1. Just get rid of all factors of 2. Something like:
    let max = 1;
    while (n % 2 === 0) { max = 2; n /= 2; }
    After this run the max will either be 1 or 2 (If it was an even number).

  2. Now you just need to check all the odd numbers
    let f = 3;
    while (f * f <= n) {
    if (n % f === 0) { max = f; n /= f; }
    else { f += 2; }
    }

5

This topic was automatically closed after 60 days. New replies are no longer allowed.