Find the 10001st Prime Number
- Time:2020-09-10 12:55:33
- Class:Weblog
- Read:37
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:Bruteforce with Memoization to Count the Square Digit Chains
How to Merge Two List/Iterators in Java?
How to Design a First Unique Number Class with O(1)?
Get Help With SQL Database Design and Development For Your Busin
Compute the Minimum Value to Get Positive Step by Step Sum using
3 Day-One Mistakes that Spell Long Term Trouble for B2C Blogs
Clever Offline Techniques to Improve Brand Visibility and Deadly
7 Best Related Posts Plugins for WordPress for 2020
5 Ways to Grow Your Blog’s Subscriber List
Best Video Specs for Facebook
- Comment list
-
- Comment add