Project Euler 7: 10001st prime

10001st Prime


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?

Official Problem

Solution Approach

In this problem of the 10001st prime, we have to find the 10001st prime number. A prime number is a natural number that is greater than 1 and is not a product of 2 smaller numbers.

We will find out the prime numbers using brute force but we will do it smartly so that the complexity decreases. We will check if a number is prime by diving it by 2,3 and then dividing by only odd numbers. This will continue till we reach the square root of the number. If it is not divisible by any number till that time then we can tell that it is prime. In case the number is divisible by any number before that, it is not a prime. We will continue to find the prime number in this way until we get the 1001st prime.

The time complexity of this approach is O(nlog n) as we need to iterate till 10001st prime and we have to check if each number is prime or not. The space complexity of this approach is constant i.e O(1) as we just need to store the count value.

Coming to the code part of the approach we can declare a count variable to check if we got the 10001st prime or not. Then we run a loop without the test condition. We check the numbers for prime and if they are prime we keep increasing the count. If we count becomes 10001 we get out of the loop after printing that number.

Solution Code

Java Solution

Python Solution

For more Project Euler explained solutions visit Project Euler Detailed Solutions.

For Leetcode detailed solutions go to Leetcode Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding 🙂

Leave a Comment

Your email address will not be published. Required fields are marked *