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) —
GD Star Rating
loading...
279 wordsloading...
Last Post: The Difference Between Sum of Squares and Square of the Sum
Next Post: How Many Squares/Rectangles Does a Rubik Cube Have?
