Possible Infinite Loop Detected (false flag?) [SPOILER INSIDE] || Project Euler: Problem 3

JavaScript
1

Hey all,

I have been doing the Euler challenge and, on problem 3 (largest prime factorial) I get the hint that a possible infinite loop is detected but I cannot see that being the case as my code has breaks/return statements and the loops are limited by the input number. Obviously, I know putting a huge number would take a lot of time to compute but that is always going to be the case, isn’t it?

Thought I’d ask here whether I am wrong and the warning is real or whether I am right in believing it is a false flag due to the possible size of the computation required by a large number.

The tests all pass, just made me wonder if I have missed something.

Thanks all.

My code is as follows:

function largestPrimeFactor(number) {
    if(isPrime(number)) return number;
    return primeFactors(number);
  }
  
  function isPrime(num) {
    if(num <= 3) return true;
    for( let i = 2; i < num; i++) {
      if(num % i === 0) return false;
    }
    return true;
  }
  
  function primeFactors(num) {
    let primeFact;
    for(let i = 2; i < num; i++) {
      if(isPrime(i) && num % i === 0) primeFact = i;
    }
    return primeFact;
  }
  
  largestPrimeFactor(13195);

Figured it out, thanks to Bob and having a peek at the official solution. Final solution without warning is as follows:

function largestPrimeFactor(number) {
    // Set the starting prime
    let prime = 2,
        rtn = 1;
    // Initiate a loop which will only run while
    // prime is less than number
    while (prime <= number) {
        // Check that the current prime is a factor of the current number
        number % prime === 0 ?
            // if it is set the return value to the current prime
            (rtn = prime,
                // Then decrement the initial number so we can start from there
                // on the next run
                // If it isn't factor increment the current prime
                number /= prime) : prime++;
    }
    // Return the final value.
    return rtn;
}

largestPrimeFactor(13195);
2

I believe your code will work, but it’s extremely inefficient. Does it work for smaller composite numbers? That would tell you if the code is actually correct.

You can, at the very least, tighten up those loop bounds (Quite a bit in fact! What is the largest possible value that is needed to check as a divisor for primality? It’s not num-1!).

Also, I would rearrange your conditionals to take advantage of short circuiting. (mod is cheaper than isPrime)

6

WRT to loop bounds, you can do better than num/2, but that’s the right line of thinking. Hint: by checking if n % 2, you are also checking n % (n/2). How far do you need to follow this pattern?

WRT short circuiting, I meant that num % i is cheaper to evaluate than isPrime(i). If there are significantly different computational costs for an &&, then you should put the cheaper one first. If the first condition is not met, then the second, more expensive condition will not be evaluated.

1 Like
7

WRT to loop bounds, you can do better than num/2 , but that’s the right line of thinking. Hint: by checking if n % 2 , you are also checking n % (n/2) . How far do you need to follow this pattern?

Thanks, mate. My initial thinking was that I needed to find out whether n was, itself, a prime number. If so just return that. My logic was simply that the best way of doing so would be to try and divide it by all numbers lower than it (or half of it as, realistically, anything above the halfway mark would ultimately not be a factor for obvious reasons). The fact that n % 2 would also check the halved variant of the number went over my head :sweat_smile:

WRT short circuiting, I meant that num % i is cheaper to evaluate than isPrime(i) . If there are significantly different computational costs for an && , then you should put the cheaper one first. If the first condition is not met, then the second, more expensive condition will not be evaluated.

Riiight! I get you now, by changing the order or better yet just removing the isPrime issue I could have just cut out straight after checking whether the num % i === 0 parameter was true!

Thank you for explaining mate, I appreciate it.

1 Like