Project Euler: #7 - 10001st prime

Problem

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?

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 10001st 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!

Project Euler: #7 - 10001st prime

Comments

Project Euler: JS Solution Explained!

Project Euler: #8 - Largest product in a series

More from this blog

What is JavaScript and How It Powers Modern Websites

Project Euler: #17 - Number letter counts

Project Euler: #16 - Power digit sum

Project Euler: #15 - Lattice paths

Project Euler: #14 - Longest Collatz sequence

Problem

Problem Description

Approach

Solution

Command Palette

Comments

Project Euler: JS Solution Explained!

Project Euler: #8 - Largest product in a series

More from this blog

Problem

Problem Description

Approach

Solution