Find the 10001st Prime Number
- Time:2020-09-10 12:55:33
- Class:Weblog
- Read:28
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:Digital Business Cards App Will Change The Way You Network Forev
3 Things You Need To Know When Launching Your Startup’s Blog
Instagram Influencer Marketing Is A Billion Dollar Industry [Inf
5 Social Adverts for Driving Stellar Webinar Attendance (Infogra
5 Ways to Serve Up a Tastier Food Blog to Your Audience
Meet These Single Moms That Created Successful Blogs
Boost Your SERP Rankings with Better Marketing Automation
How to Turn Your Withering Blog Posts into Fully-Fledged Plants
The Emoji Evolution: How Your Brand Can Use Emojis
6 Tips to Get Started With Selling on Your Blog
- Comment list
-
- Comment add