nth Prime Number in Java

A number is considered prime if only divisible by one and itself. Prime numbers include, for example, 2, 3, 5, 7, 11, etc. In looking at it another way, a prime number is a natural number that divides evenly into the numbers 1 and itself by approximately two different natural numbers. Take note that 0 and 1 are not prime numbers. All other even numbers may be divided by 2, making the number 2 the only even prime number. 

There are two ways to find the nth Prime Number

1. Applying a Simple/Traditional Approach

2. Using Eratosthenes' Sieve as a Guide

Applying a Simple/Traditional Approach

The fundamental approach for finding the nth prime number. The steps are described below. 

• Read from the operator an integer (num).
• Put the (ct!=num) condition within the while loop. The variable c starts as 0 and counts all detected prime numbers.
• For the next number check, add 1 to variable I (which had a value of 1).
• Verify whether or not variable I am a prime.
• If so, add one to the variable ct.

Filename: NthPrime1.java

//Program for finding the nth prime number
//importing the packages
import java.io.*;
import java. util.*;
import java. util.Scanner;  
public class NthPrime1
{  
public static void main(String[] args)   
{  
//Scanner class 
Scanner sc = new Scanner(System.in);  
System. out.print("Enter the number: ");  
// the number is read by the user
int num = sc.nextInt();   
int number=1, ct=0, i;  
while (ct < num)  
{  
number=number+1;  
for (i = 2; i <= number; i++)  
{   
// checks for numbers having 2 factors  
if (number % i == 0)   
{  
// if the condition becomes true, then exit out of the loop  
break;  
}  
}  
if (i == number)  
{  
// the value of ct is incremented to 1
ct = ct+1;  
}  
}  
// displaying the nth prime number
System.out.println("The " +num +"th prime number is: " + number);  
}  
}  

Output

Enter the number: 14
The 14th prime number is: 43

Explanation:

A user-input integer has been taken and stored in the variable num. The variable num has its value increased by 1 whereas if while loop returns true. The while loop is indefinite if the ct variable's value exceeds num.

When a condition is met, the variable number is divided by i each time, and the result is checked against 0.

After that, a for loop is created, and i is initialized with 2 to start it off. Until the i=number condition returns true, the for loop runs. The loop is broken, and the next line that determines whether or not i is equal to the number is executed if the result equals 0.

2. Using Eratosthenes' Sieve as a Guide

An ancient procedure known as the Sieve of Eratosthenes allows us to locate all prime numbers up to a certain value (limit). It does this by noting and recognizing the multiples of each prime number, beginning with the initial prime number (2). The resulting unmarked numbers are prime numbers once each prime's multiples have been designated composite (not prime) numbers. The method has a computational complexity of O(n) and consumes O(n) memory (nloglogn). The best case scenario for n<10,000,000 is that it is the most effective way of finding all prime numbers lower than n.

Approach

First, apply the Sieve of Eratosthenes procedure to locate all the prime numerals inside the specified range.

All prime numbers should be kept in a vector.

Return an element at the (N-1)th index in a vector for a given integer N.

Algorithm

• Make a list of consecutive numbers in the range 2 to n.
• Let t= 2. The initial prime number, 2, has been taken into consideration.
• Each number larger than or equal to t2 itself should be marked in the list starting at t2, counting up in increments of t. There will be t(t+1), t(t+2), t(t+3), etc. in these values.
• Identify the first higher-than-t number in the list which is not marked. Only stop if there is a number like that. If not, set t to this value (the subsequent prime), and proceed from step 3 as before.

All the numbers that are left after terminating the algorithm are prime.

 Filename: NthPrime2.java

//Program for finding the nth prime number
//importing the packages
import java.io.*;
import java.util.*;
import java.util.ArrayList;  
public class NthPrime2  
{  
// declaring the max size 
static int MAX_SIZE = 1000005;  
// an object is created for storing the prime numbers
static ArrayList numlist = new ArrayList();  
//implementing a static function that uses the Sieve of Eratosthenes method to determine the nth prime number 
static void findNthPrimeNumber()   
{   
// a boolean Array is created and initialized to 0  
// the value become false if it is not the prime number  
boolean [] IsPrimes = new boolean[MAX_SIZE];   
for(int i = 0; i < MAX_SIZE; i++)  
IsPrimes[i] = true;  
for (int t = 2; t * t < MAX_SIZE; t++)   
{   
// if the value of IsPrimes[t] is not changed
// then the number is prime  
if (IsPrimes[t] == true)   
{   
//identifies the multiples of p that are bigger than or equal to the square of that number 
//The values multiples of p and less than p to power 2 have already been indicated.
for (int i = t * t; i < MAX_SIZE; i += t)   
IsPrimes[i] = false;   
}   
}   
for (int t = 2; t < MAX_SIZE; t++)   
if (IsPrimes[t] == true)   
// the prime number is pushed to ArrayList  
numlist.add(t);  
}   
// main code
public static void main (String args[])   
{  
/// the function findNthPrimeNumber() calling 
findNthPrimeNumber();  
// the get() method will return the position value in the list 
System.out.println("The 6th prime number is " + numlist.get(5));  
System. out.println("The 24th prime number is " + numlist.get(23));  
System.out.println("The 1000th prime number is " + numlist.get(999));  
}  
}   

Output

The 6th prime number is 13
The 24th prime number is 89
The 1000th prime number is 7919