Project Euler 7: 10001st prime - Project Euler Detailed Solutions

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?

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

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution{
	public static boolean isPrime(int n){
	  if(n%2==0) return false;
	  else {
	    for(int i=3; i<= (int)Math.sqrt(n); i+=2){
	      if(n%i==0) return false;
	    }
	  }
	  return true;
	}
	
	public static void main (String[] args)
	 {
    int count = 1;
    for (int i=3; ;i++){
      if(isPrime(i)) count++;
            
      if(count == 10001) {
        System.out.println(i);
        break;
      }
    }
  }		
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Solution{

public static boolean isPrime(int n){

if(n%2==0) return false;

else {

for(int i=3; i<= (int)Math.sqrt(n); i+=2){

if(n%i==0) return false;

}

return true;

}

public static void main (String[] args)

{

int count = 1;

for (int i=3; ;i++){

if(isPrime(i)) count++;

if(count == 10001) {

System.out.println(i);

break;

}

Python Solution

import math

def is_prime(n):
  if (n%2==0): return False
  else: 
    for i in range(3, int(math.sqrt(n))+1):
      if n%i == 0:
        return False
        
  return True
  
  
def calculate_1001st_prime():
  count = 1
  i = 3
  while(True):
    if is_prime(i):
      count += 1
    if count == 9:
      print(i)
      break
    i+=1

calculate_1001st_prime()

import math

def is_prime(n):

if (n%2==0): return False

else:

for i in range(3, int(math.sqrt(n))+1):

if n%i == 0:

return False

return True

def calculate_1001st_prime():

count = 1

i = 3

while(True):

if is_prime(i):

count += 1

if count == 9:

print(i)

break

i+=1

calculate_1001st_prime()

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 🙂

Problem

Solution Approach

Solution Code

Java Solution

Python Solution

Leave a Comment Cancel Reply