Find the 10001st Prime Number
- Time:2020-09-10 12:55:33
- Class:Weblog
- Read:32
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 Remove Items/Entries with Specific Values from Map/HashMa
Find the Real Root of 4^x + 6^x = 9^x
Depth First Search (Backtracking) Algorithm to Solve a Sudoku Ga
Using Bitmasking Algorithm to Compute the Combinations of an Arr
Flashing the BIOS of HPZ800 Server to 3.61 Rev.A
Algorithm to Sum The Fibonacci Numbers
How to Adapt Your Blog to Increasing Zero-Click Searches
Understanding Marketing Automation & Its Perks for Your Busi
Adobe Flash Player Nears its EOL, Will this Affect your Blog?
How to Create Unique Content through User Personas
- Comment list
-
- Comment add