Project Euler problem 3: Largest prime factor in JavaScript

Question

I have created a soloution for Project Euler: Problem 3 - Largest Prime Factor in JavaScript:

function isPrime(value) {
    for (var i = 2; i < value; i++) {
        if (value % i == 0) {
            return false;
        }
    }
    return true;
}

function findFactors(value) {
    var array = [];
    for (var i = 2; i < value; i++) {
        if (value % i == 0) {
            array.push(i);
        }
    }
    return array;
}

function findPrimeFactors(value) {
    var array = [];
    for (var i = 0; i < findFactors(value).length; i++) {
        if (isPrime(findFactors(value)[i])) {
            array.push(findFactors(value)[i]);
        }
    }
    return array;
}

document.write("Answer: " + Math.max(...findPrimeFactors(600851475143)));

I would like to know if my code even works, as it is so slow, that even when I left it for 20 minutes it still didn't finish, and if so, I would like to know a quick way of doing it (If my code would actually give it) so I can mark it as completed.

200_success · Accepted Answer · 2017-09-23 08:43:57Z

Your code looks pretty, and it is a very literal naïve implementation of the requirements. Unfortunately, the algorithm you are using is extremely inefficient.

Factoring large numbers is hard work! The difficulty of factoring large numbers is, in fact, what keeps cryptographic algorithms like RSA safe. In your findFactors() function, just counting up to 600 billion will take a while; having to check for divisibility within the loop is even slower!

For a quick algorithm that will give the answer in about one second, see this answer.

Przemek · Accepted Answer · 2017-09-25 09:56:13Z

Remarks

You have translated your problem into code in a pretty literal and straight-forward, but insanely inefficient way. You are not relying on any mathematical properties, trying to solve everything in a brute-force fashion. Remember, that Project Euler is a set of programming challenges that are math-oriented, though. Three more far less important things to note:

Use identity operator wherever applicable,
array.push(…) is somewhat less efficient than array[array.length] = …,
document.write(…)? Oh, c'mon.

Solution

It doesn't really get more efficient and concise than that, in JavaScript:

const largestPrimeFactor = n => {
    let i = 2;
    while (i * i < n) {
        while (n % i === 0) { n /= i; }
        i++;
    }
    return n;
};

console.log(largestPrimeFactor(600851475143));

.as-console-wrapper { top: 0; }

Stack Exchange Network

Project Euler problem 3: Largest prime factor in JavaScript

2 Answers 2

Remarks

Solution

You must log in to answer this question.

Hot Network Questions

Project Euler problem 3: Largest prime factor in JavaScript

2 Answers 2

Remarks

Solution

You must log in to answer this question.

Related

Hot Network Questions