How to find the nth prime number in Java?

Java

Can someone help me with the code to find the nth prime number in Java? I am practicing for a coding competition and was stuck with this! I tried few things but those exceeded the time limit. So can someone help me with the problem?

2
Answers

Replies

import java.util.Scanner;


public class NthPrime {


  public static void main(String[] args) {


    Scanner sc = new Scanner(System.in);


    System.out.print("Enter n to compute the nth prime number: ");


    int nth = sc.nextInt(); 


    int num, count, k;


    num=1;


    count=0;


 


    while (count < nth){


      num=num+1;


      for (k = 2; k <= num; k++){ //Here we will loop from 2 to num


        if (num % k == 0) {


          break;


        }


      }


      if ( k== num){//if it is a prime number


        count = count+1;


      }


    }


    System.out.println("Value of nth prime: " + num);


  }


}

 

There are several ways to find the nth prime number in java but we follow the simple way using Sieve of Eratosthenes


For Example:


import java.util.*; 

public class NthPrimeNumber



public static void main (String[] args) 



 

// Instantiates variable n 

int n = 500; 

 

// LinkedList is a container to save 

// all the prime number less than 500

LinkedList ll = new LinkedList();

boolean [] prime_arr = new boolean[n]; 

 

for(int p = 0; p < n; p++) 

prime_arr[p] = true; 

 

for (int q = 2; q * q < n; q++) 



// If it is a prime then check for its

// multiples

if (prime_arr[q] == true) 



// It marks all multiples of q and less

// than q^2

for (int p = q * q; p < n; p=p+q) 

prime_arr[p] = false; 





 

// This LinkedList contains all the

// prime number less than 500

for (int q = 2; q < n; q++) 

if (prime_arr[q] == true) 

ll.add(q); 

    System.out.println("All Prime less than 500: "+ll);


 

    // To find any nth prime number less than 500

    // starting from the 1st prime number to 

    // 95th prime number

System.out.println("1st prime number is " + 

ll.get(0));

System.out.println("2nd prime number is " + 

ll.get(1));

System.out.println("94th prime number is " + 

ll.get(93));

System.out.println("95th prime number is " + 

ll.get(94)); 

 

}


Output:


All Prime less than 500: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499]


1st prime number is 2


2nd prime number is 3


94th prime number is 491


95th prime number is 499



In the above code, we can find any nth prime number less than 500 and starting from the first prime number(1st prime number) to 95th prime number. If you want to calculate any other nth prime number greater than 95th prime number(i.e. If you expect any nth prime number greater than 500) then you can achieve this by increasing the size of n.



The Sieve of Eratosthenes algorithm is used to calculate the nth prime number starting from 1st prime number to 95th prime number and it is used to optimize the code of finding nth prime number and the methodology are given below:



In the first step, we have a list of n integers and here the value of n = 500 and the elements starting from 2 so the list elements are [2,3,4,5…………..500] and the element 1 is not included because it is not a prime.



In the second step, we pick a first element from the list i.e. (2) and then check for prime. If it is prime then we cross or mark all the multiples of the prime number 2 in the list because any multiple of the prime number 2 is not a prime. So all the multiples of 2 in the list are [4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110………496,498,500]. The modified List is [2,3,5,7…………495,497,499].



In the third step, we pick a next available element from the list i.e. (3) and then check for prime. If it is prime then we cross or mark all the multiples of the prime number 3 in the list because any multiple of the prime number 3 is not a prime. So all the multiples of 3 in the list are [6,9,12,15,18,21,24,27,30,33,36,39,42,45,48………...495]. The modified list are [2,3,5,7,11……….493,497,499] and next we pick a number from the list i.e. (5) and the process repeats again and again till the second multiples of any prime number whose values are greater than any number in the list.


 


For Example: when we pick 251 from the list and it is a prime number and all the multiples of 251 are greater than 500 which is not in the list. So our search was completed at 251.



In the last step, The final modified list are [2,3,5,7,11,13,17,19,23,29………...497,499] and all the elements contains in the list are prime elements and the element points at the last index in the list are nth element (i.e. the last element in the list are nth element that is prime).

 
 

If you want to unleash your potential in this competitive field, please visit the Java course page for more information, where you can find the Java tutorials and Java frequently asked interview questions and answers as well.

 

This topic has been locked/unapproved. No replies allowed

Login to participate in this discussion.

Leave a reply

Before proceeding, please check your email for a verification link. If you did not receive the email, click here to request another.