Table of contents
Problem
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13
, we can see that the 6
th prime is 13
.
What is the 10001
st prime number?
Problem Description
We all know about Prime Numbers. A number that is divisible by 1
and itself
is called a Prime Number. In other words, it has only 2 factors - 1
and itself
.
So we need to find the nth
prime number. For example, 3rd
prime number is 5
, 4th
prime is 7
, 6th
prime is 13
, 10th
prime is 29
and so on.
We need to find the 10001
st prime number.
Approach
To find nth
prime number, we need to loop through a range of numbers from 2
to Number.MAX_SAFE_INTEGER
.
Increase the counter by 1
for each prime number and once we find the nth
prime, we break out of the loop.
To Check for the prime number, we use the same technique as in Problem #3 Largest prime factor
Solution
const isPrime = num => {
if (num === 1) return false;
if (num === 2 || num === 3) return true;
if (num %2 === 0 || num % 3 === 0) return false;
for (let i = 5; i <= Math.ceil(num / 2); i += 6) {
if (num % i === 0 || num % (i+2) === 0) return false;
}
return true;
}
let count = 0;
for (let i = 2; i < Number.MAX_SAFE_INTEGER; i++) {
if (isPrime(i)) count++;
if (count === n) {
console.log(i);
break;
}
}
console.time("10th");
console.log(nthPrime(10)); // 29
console.timeEnd("10th"); // 10th: 0.221923828125 ms
console.time("100th");
console.log(nthPrime(100)); // 541
console.timeEnd("100th"); // 100th: 0.68701171875 ms
console.time("10001th");
console.log(nthPrime(10001)); // 104743
console.timeEnd("10001th"); // 10001th: 827.61181640625 ms
You can find my solution on GitHub 07
This particular solution was timed out
in Hacker rank for 2 out of 7 test cases. So a little bit of tweaking is necessary to achieve a better time complexity.
If you have a better solution, please leave it in the comments below.
But no worries, the above code works perfectly fine for our use case, 10001th
prime number.
For the other Project Euler Solutions, please follow the series Project Euler Solutions in JS.
Thank you!