Project Euler: Problem 3

Posted on October 17th 2020 in Algorithms by Pim Debaere.

Project Euler: Problem 3

Don't read further if you don't want a spoiler, because today I'm going to dive into Project Euler's third problem. A problem with prime numbers this time.

Largest prime factor

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

What is the largest prime factor of the number 600851475143?
Problem 3

We will have to iterate over all numbers to see if this is a prime factor of the given number. Here I want to point out that we will not have to do this over the entire number. Each number can have a maximum of one prime factor that is greater than √n.

So every time, after division by a prime factor, we can use the square root of the remaining factor as the limit. When this factor is greater than that square root, we will have the largest factor. This is how I came to the following implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function largestPrimeFactor(n) {
  var ret = 0;
  
  for (var i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return largestPrimeFactor(n / i);
    }
  }

  return ret === 0 ? n : ret;
}

console.time('run');
var answer = largestPrimeFactor(600851475143);
console.timeEnd('run');
console.log('Answer: ' + answer);

// output:
// run: 0.56005859375ms
// Answer: 6857

Fig. 1 – Project Euler: Probleem 3 - een uitwerking van het probleem.

Please note that in the code above I trust the input, but you can easily check whether n > 1, since 0 and 1 cannot be factored into prime factors.