1
\$\begingroup\$

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.

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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; }

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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