Project Euler: Problem 7

Posted on November 20th 2021 in Algorithms by Pim Debaere.

Project Euler: Problem 7

A simple question from Project Euler, as usual, and – also as usual – a warning not to read further if you don't want to deprive yourself of the pleasure of looking for the solution.

10 001st prime number

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?
Problem 7

We have no idea what value to expect here, so we have no choice but to calculate. Preferably in an efficient way of course. Some facts that can help us:

the number 1 is not prime;
except for the number 2, all primes are odd;
all primes greater than 3 can be written as 6n + 1 or 6n – 1 (see also PrimePages;
any number n can have only one prime factor greater than √n.

The consequence of the prime number test for a number n is, if we do not find a number less than or equal to √n that is a divisor of n, that n is a prime number. The only prime factor of n is then n itself.

If we now merge the above into an algorithm, we get something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function isPrime(n) {
  if (n === 1) return false; // 1 is not prime
  if (n < 4 ) return true; // 2 & 3 are prime
  if (n % 2 === 0 ) return false; // exlude other even numbers
  if (n < 9) return true; // 5 & 7 are prime
  if (n % 3 === 0) return false; // exclude multiples of 3

  var r = Math.floor(Math.sqrt(n));
  var factor = 5;

  while (factor <= r) {
    if (n % factor === 0) return false; // check 6x-1
    if (n % (factor + 2) === 0) return false; // check 6x+1

    factor += 6;
  }

  return true;
}

Fig. 1 – Project Euler: Problem 7 - algorithm for determining whether a given number is prime.

Now that we have a function to determine whether or not a number is prime, all we have to do is find the 10 001st prime.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
console.time('run');
var limit = 10001;
var i = 1; // start with 1, because we know 2 is prime
var ret = 1;

do {
  ret += 2;

  if (isPrime(ret)) i++;
} while (i < limit);

console.timeEnd('run');
console.log('Answer: ' + ret);
// output:
// run: 6.352783203125 ms
// Answer: 104743

Fig. 2 – Project Euler: Problem 7 - using the algorithm.