Find the 10001st Prime Number

  • Time:2020-09-10 12:55:33
  • Class:Weblog
  • Read:38

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 10001st 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.

1
2
3
4
5
6
7
8
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;
}
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:

1
2
3
4
5
6
7
8
9
10
11
12
function findNthPrime(N) {
  let prime = 2;
  let i = 1;
  while (i < N) {
    do {
        prime ++;
    } while (!isPrime(prime));
    i ++;
  }
  return prime;
}
console.log(findNthPrime(10001));
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
  }
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) —

Recommend:
How To Use Twitter To Get New Clients
How to Turn Your Best Blog Posts Into Even Better Videos
Why You Need Influencers for Your Brand In 2019
How to Use a Blog to Increase Ecommerce Sales
Why conducting a website audit is important
How to Write a Great Blog Post for a Global Audience
Top Reasons Why Your Blog Sucks at Making Money (and How to Fix
How To Write A Great Product Placement Blog Post
Structured Data for SEO Blogging
5 Ways a Blog Can Help Your Business Grow
Share:Facebook Twitter
Comment list
Comment add