Largest prime factor of a given number

Question

I'm solving Problem 3 in Project Euler:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Most answers I found made use of array to store the prime factors and iterate over them to find the greatest one which doesn't seem good.

I'm recently learning js and this doesn't seem to me quite javascript-ish way of doing. Is there any way to refactor this?

var highestPrime = 2;
function divide (limit){
    for (var i=3; i<Math.floor(limit/2)+1; i++) {
        if (limit%i == 0){
            compareIfEven(i); // callback to check if it's even divisor
        }
    }
return highestPrime;
}

function compareIfEven(i){
    if (i % 2 !== 0){
        compareIfPrime(i);  // if not even, callback to compare if it's prime
    }
}

function compareIfPrime(i) {
    for (var j=3; j<i; j++) {
        if (i%j !== 0){  // if a prime divisor, assign it the value highestPrime
            highestPrime = i;
        }
    }
}
console.log(divide(600851475143));

It works for smaller values but goes over memory limit for asked value. Is there any way to make it efficient?

Answer 1

I don't think the code is working at the moment, but assuming it is a minor issue, here are my observations:

1. Your comments are not really helpful. For instance, in the comment below, it is obvious to anyone reading the code that the function 'compareIfEven' is being called. You could rather explain how it fits into your algorithm.

       compareIfEven(i); // callback to check if it's even divisor
   

   Also, it is technically not a callback, it is a function call.

2. Function names are primitive. You could make your code easier to understand simply by renaming divide to getLargestPrimeFactor and renaming compareIfEven to something like checkIfEven or simply isEven.

3. Your choice of algorithm is also suboptimal. You are iterating from 3 towards higher numbers, while in fact, if you were to iterate from higher numbers to 2, the first prime you get would be your answer.

4. Also you could improve performance by using Math.floor(Math.sqrt(limit)) rather than just a Math.floor(limit/2).

5. You could skip the compareIfEven function entirely if you incremented index i by 2 rather than 1. Through this all the divisors will be odd numbers and number of iterations will reduce by roughly 50%.

   Note: If you are pulling off something like that a good idea would be to document it in comments for others.

6. Variable names could be more meaningful. Just one example, limit could be replaced by number. As it stands limit prompts me to wonder about some kind of limit that number poses, while in fact, it is just a number.

Hope this helps.

Btw, I think the problem is in the last function compareIfPrime. You may want to check out some algorithms for prime checking online.