Robert Eisele
Engineer, Systems Architect and DBA

Project Euler 7: 10001st prime

Problem 7

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?

Solution

The easiest way to solve this problem is checking number by number if it's a prime and if so, incrementing a counter until 10001. Since every prime after 2 is odd, we can increment by two, which halves the actual search space. An implementation can then look as follows:

function solution(L) {

  var c = 1;
  var n = 1;

  while (c < L) {

    n+= 2;

    if (isPrime(n)) {
      c++;
    }
  }
  return n;
}
solution(10001);

A function isPrime is used in the solution. A primal check can be done by  looping from 2 to \(n\) and check if any number on the way divides our number. If not, we found a prime. One optimization is to loop to \(\sqrt{n}\) instead of the whole space, since only multiples of already known primes remain above the limit. What we also can do is unrolling checks of multiples of 2 and 3, which allows us to loop in a stepwidth of 6, which however requires a check of every \(i+2\) as well. The implementation can then be stated as:

function isPrime(n) {

  if (n < 2)
    return false;

  if (n % 2 === 0)
    return n === 2;

  if (n % 3 === 0)
    return n === 3;

  var h = Math.floor(1 + Math.sqrt(n));
  var i = 5;

  while (i <= h) {
    if (n % i === 0)
      return false;
    if (n % (i + 2) === 0)
      return false;
    i+= 6;
  }
  return true;
}

As such, the complexity of isPrime is bound to \(O(\sqrt{n})\), which results in an overall complexity of \(O(n\sqrt{n})\), which is much better than a sieve approach I tried before.

Go to overview