nth Prime Number Java

A number is prime if it is divisible by 1 and itself. In other words, a prime number is a natural number with exactly two distinct natural number divisors 1 and itself. For example, 2, 3, 5, 7, 11, etc. are the prime numbers. Note that 0 and 1 are not prime numbers. The number 2 is the only even prime number because all the other even numbers are divisible by 2. In this section, we will learn how to find the nth prime number in Java.

There are two ways to find the nth prime number in Java:

  • Using Basic/ traditional Approach
  • Using Sieve of Eratosthenes Approach

Using Basic/ traditional Approach

In the basic approach, we follow the same approach that we have used to find the prime number. Follow the steps given below.

  • Read an integer (n) from the user.
  • In the while loop, execute the condition (c!=n). Initially, the variable c is 0 and counts the discovered prime numbers.
  • Increment the variable i (initially 1) by 1 for the next number check.
  • Check if the variable i is prime or not.
  • If yes, increment the variable c by 1.

Let’s find the nth prime number through a Java program using a while loop.

NthPrimeNumberExample.java

  1. import java.util.Scanner;  
  2. public class NthPrimeNumberExample   
  3. {  
  4. public static void main(String[] args)   
  5. {  
  6. //constructor of the Scanner class  
  7. Scanner sc = new Scanner(System.in);  
  8. System.out.print(“Enter the value of n to compute the nth prime number: “);  
  9. //reading an integer from the user  
  10. int n = sc.nextInt();   
  11. int num=1, count=0, i;  
  12. while (count < n)  
  13. {  
  14. num=num+1;  
  15. for (i = 2; i <= num; i++)  
  16. {   
  17. //determines the modulo and compare it with 0   
  18. if (num % i == 0)   
  19. {  
  20. //breaks the loop if the above condition returns true  
  21. break;  
  22. }  
  23. }  
  24. if (i == num)  
  25. {  
  26. //increments the count variable by 1 if the number is prime  
  27. count = count+1;  
  28. }  
  29. }  
  30. //prints the nth prime number  
  31. System.out.println(“The ” +n +”th prime number is: ” + num);  
  32. }  
  33. }  

Output 1:

Enter the value of n to compute the nth prime number: 3
The 5th prime number is: 5

Output 2:

Enter the value of n to compute the nth prime number: 25
The 25th prime number is: 97

We have taken an integer from the user and store it in the variable n. The while loop continues until the value of the count variable is less than n. If the while loop returns true, the value of the variable num is incremented by 1.

After that, a for loop comes into existence that begins with the initialization of i by 2. The for loop executes until the condition i<=num returns true. Every time when the condition returns true, it divides the variable num by i also compare the resultant with 0. If the resultant is equal to 0, the loop breaks and jumps to the next statement that compares i is equal to num or not. If the variable i is equal to num, the value of the variable count is incremented by 1.

After that, the control again moves to the while loop. On terminating the while loop, we get the nth prime number.

Let’s see another approach to find the nth prime number.

Using Sieve of Eratosthenes Approach

The Sieve of Eratosthenes is an ancient algorithm through which we can find the prime numbers up to a specified number (limit). It does so by identifying and marking the multiples of each prime number, starting from the first prime number 2. When all the multiples of each prime are marked as composite (not prime), the remaining unmarked numbers are prime numbers. It is the most efficient approach to find all the prime numbers smaller than n (better for n<10,000,000). The approach consumes the O(n) of the memory and its time complexity is O(nloglogn). Let’s see what should be the approach.

Approach

  • First, find all the prime numbers up to the given limit using the Sieve of Eratosthenes algorithm.
  • Store all the prime numbers in a Vector.
  • For a given number N, return the element at (N-1)th index in a vector.

Algorithm

  • Generate a list of consecutive integers starting from 2 to n.
  • Initially, let p=2. We have considered that the first prime number 2 is p.
  • Starting from p2, count up in increments of p and mark each of these numbers greater than or equal to p2 itself in the list. These numbers will be p(p+1), p(p+2), p(p+3), etc.
  • Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

After terminating the algorithm, all the numbers that are not marked are prime.

Example

Let’s understand the above approach through an example.

Suppose, we want to find all the prime numbers less than or equal to 20 (n). So, we need to print all the prime numbers less than or equal to n. Let’s create a list of the numbers starting from 2 to 20.

nth Prime Number Java

In the above table, mark all the numbers that are divisible by 2 (we have marked by red color), also greater than or equal to the square of it.

nth Prime Number Java

After the first prime (2) and unmarked number, the next unmarked number is 3. Now we will mark the numbers that are divisible by 3 (we have marked by blue color), also greater than or equal to the square of it.

nth Prime Number Java

The next unmarked prime number in the table is 5, so we will mark the numbers that are divisible by 5, also greater than or equal to the square of it. The numbers that are divisible by 5 are 10, 15, and 20 that are already marked. Hence, there is no number to mark.

nth Prime Number Java

In the above table, unmarked numbers are:

nth Prime Number Java

Hence, we get the prime numbers (2, 3, 5, 7, 11, 13, 17, and 19).

NthPrimeNumber.java

  1. import java.util.ArrayList;  
  2. public class NthPrimeNumber  
  3. {  
  4. //declare the maximumm size as constant   
  5. static int MAX_SIZE = 1000005;  
  6. //creating an instance of the ArrayList class that stores all the prime numbers  
  7. static ArrayList<Integer> primelist = new ArrayList<Integer>();  
  8. //defining a static function to find the nth prime number using Sieve of Eratosthenes approach  
  9. static void findnthPrimeNumber()   
  10. {   
  11. //creating a boolean array and marking all entries as true  
  12. //the value IsPrime[i] will be false if i is not a IsPrime  
  13. boolean [] IsPrime = new boolean[MAX_SIZE];   
  14. for(int i = 0; i < MAX_SIZE; i++)  
  15. IsPrime[i] = true;  
  16. for (int p = 2; p * p < MAX_SIZE; p++)   
  17. {   
  18. // If IsPrime[p] is not changed,   
  19. // then it is a prime   
  20. if (IsPrime[p] == true)   
  21. {   
  22. //finds the multiples of p greater than or equal to the square of it  
  23. //we have already marked the numbers that rae multiple of p and are less than p to the power 2   
  24. for (int i = p * p; i < MAX_SIZE; i += p)   
  25. IsPrime[i] = false;   
  26. }   
  27. }   
  28. for (int p = 2; p < MAX_SIZE; p++)   
  29. if (IsPrime[p] == true)   
  30. //adding prime number to the ArrayList  
  31. primelist.add(p);  
  32. }   
  33. // Driver Code  
  34. public static void main (String args[])   
  35. {  
  36. //calling the static function  
  37. findnthPrimeNumber();  
  38. //get() method returns the specified position in this list  
  39. System.out.println(“7th prime number is ” + primelist.get(6));  
  40. System.out.println(“22nd prime number is ” + primelist.get(21));  
  41. System.out.println(“10000th prime number is ” + primelist.get(9999));  
  42. }  
  43. }   

Output:

7th prime number is 17
22nd prime number is 79
10000th prime number is 104729

Leave a Comment