0
\$\begingroup\$

I came up with this code after implementing the feedback given by @200_success. The previous one (A faster way to compute the largest prime factor) tested my patience, but still failed to give the answer on time. This one is an improvement as it gives the answer without much delay.

The question (Euler project problem #3)

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

What is the largest prime factor of the number 600851475143 ?

Logic:

Keep dividing the number n by all the factors, starting from the smallest one. The value of n left in the end will be the largest prime factor of the original value of n.

My code:

function problem3(n){
    for(let i=2; i<n; i++){
        if(n%i === 0)n = n/i;
        }
    return n;
}
console.log(problem3(600851475143));

Improvement:

  • No need to loop through all the numbers below n

  • Remove the nested for loops, replacing them by only one

  • No need to check if a number is prime or not

My question: Even though it is a lot better*, but still, how can it be improved further?


* Really, it's a lot than the previous one as it used to be so slow that I never saw the output for 600851475143

\$\endgroup\$
3
\$\begingroup\$

It's buggy. Consider input 8.


Also, consider an input which is a very large prime. E.g. 2147483647. Your current code would take about 2147483645 trial divisions. It's possible to do it with only 46340 trial divisions while keeping the code very simple. Can you see how?

Hint: 46340 is the square root, rounded down.

And that's easily optimised to 23171. Can you see how?

Hint: only one prime is even.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.