# Largest prime factor of a given number

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?

• This is not working code, and is therefore not ready for review. Even if I correct the typo of fountIt for foundIt, it gives the wrong result for the test case 13195, outputting 2639 rather than 29. – Peter Taylor Nov 4 '16 at 18:21
• hi thanks for commenting my error..I've changed it and it now works. thank you :) – Bijay Timilsina Nov 5 '16 at 12:29

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.

• thanks a lot nisarg for providing such detailed insight into my code and its shortcoming...checking out my code now, i just realized that the last function was looking for largest prime divisor and not prime factor.. i will google a bit and try to solve that issue now..thanks a ton – Bijay Timilsina Nov 6 '16 at 17:54