Find the 10001st Prime Number

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

Test Prime Number

A prime number has exactly two factors: 1 and itself. Thus we can write a quick prime testing function. Please note that we only need to test up to Square Root of N, as if we find factor a, there will be N/a.

function isPrime(n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    for (let i = 2; i * i <= n; ++ i) {
        if (n % i == 0) return false;
    }
    return true;
}

The runtime complexity is O(Sqrt(N)).

Find the N-th Prime Number

Then, we can then compute the N-th prime number using the following:

function findNthPrime(N) {
  let prime = 2;
  let i = 1;
  while (i < N) {
    do {
        prime ++;
    } while (!isPrime(prime));
    i ++;
  }
  return prime;
}
console.log(findNthPrime(10001));

The answer is 104743.

We can improve a little bit, as we know that prime numbers cannot be even except 2, thus we can skip two intead of one.

function findNthPrime(N) {
    if (N == 1) return 2;
    if (N == 2) return 3;
    let prime = 3;
    let i = 2;
    while (i < N) {
      do {
          prime += 2;
      } while (!isPrime(prime));
      i ++;
    }
    return prime;
  }

–EOF (The Ultimate Computing & Technology Blog) —