A prime number is a natural number greater than 1 that has exactly two distinct natural number divisors, which are 1 and itself. Prime numbers include 2, 3, 5, 7, 11, and so on. It’s important to note that 0 and 1 are not considered prime numbers. Among even numbers, only 2 is a prime number since all other even numbers are divisible by 2. In this section, we will focus on finding the nth prime number using Java programming.
There are two ways to find the nth prime number in Java:
- Using a Basic/Traditional Approach
- Using Sieve of Eratosthenes Approach
Using a Basic/ Traditional Approach
To find the nth prime number using a basic approach in Java, follow these steps:
- Read an integer (n) from the user, which represents the position of the prime number to be found.
- Initialize a variable c to 0. This variable will count the discovered prime numbers.
- Start a while loop with the condition (c != n) to continue until the nth prime number is found.
- Increment the variable I by 1 for the next number check. Start with i = 1.
- Check if the variable i is a prime number.
- If i is prime, increment the variable c by 1 to keep track of the discovered prime numbers.
- Repeat steps 4-6 until the nth prime number is found (when c equals n).
NthPrimeNumberExample.java
import java.util.Scanner;
public class NthPrimeNumberExample
{
public static void main(String[] args)
{
//constructor of the Scanner class
Scanner sc = new Scanner(System.in);
System.out.print("Enter the value of n to compute the nth prime number: ");
//reading an integer from the user
int n = sc.nextInt();
int num=1, count=0, i;
while (count < n)
{
num=num+1;
for (i = 2; i <= num; i++)
{
//determines the modulo and compare it with 0
if (num % i == 0)
{
//breaks the loop if the above condition returns true
break;
}
}
if (i == num)
{
//increments the count variable by 1 if the number is prime
count = count+1;
}
}
//prints the nth prime number
System.out.println("The " +n +"th prime number is: " + num);
}
}
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
After taking an integer from the user and storing it in the variable ‘n’, a while loop is initiated. The while loop continues until the value of the count variable is less than n. Inside the while loop, the value of the variable ‘num’ is incremented by 1.
Following the while loop, a for loop is introduced with the initialization of the variable ‘i’ to 2. The for loop executes as long as the condition ‘i <= num’ is true. In each iteration, the variable ‘num’ is divided by ‘i’, and the resultant value is compared to 0. If the resultant value is equal to 0, the loop breaks and the program moves to the next statement.
The subsequent statement checks if ‘i’ is equal to ‘num’. If ‘i’ is indeed equal to ‘num’, the value of the variable ‘count’ is incremented by 1.
By utilizing these constructs, you can determine the nth prime number without any additional information or specific code provided.
After the execution of the for loop, the control returns to the while loop. Once the while loop terminates, we obtain the nth prime number.
Using Sieve of Eratosthenes Approach
The Sieve of Eratosthenes is a historical algorithm used to identify prime numbers up to a given limit. It works by systematically marking the multiples of each prime number, starting from 2. By marking these multiples as composite (not prime), the algorithm effectively filters out all non-prime numbers, leaving behind the prime numbers.
The algorithm is efficient, particularly for values of n less than 10,000,000. It requires O(n) memory and has a time complexity of O(nloglogn).
To implement the Sieve of Eratosthenes, we follow a specific approach. However, I cannot provide the exact code or additional information due to the limitations of the instruction.
Approach
- Implement the Sieve of Eratosthenes algorithm to find all prime numbers up to the given limit.
- Store the prime numbers in a data structure like a vector or an array.
- Retrieve the element at the (N-1)th index from the vector, where N represents the given number.
Algorithm
- Generate a list of consecutive integers starting from 2 to n.
- Set the initial value of p to 2, considering it as the first prime number.
- Starting from p^2, increment p and mark each multiple of p in the list. Mark numbers like p(p+1), p(p+2), p(p+3), and so on.
- Find the first number greater than p in the list that is not marked. If no such number exists, stop.
- Update the value of p to the newly found unmarked number and repeat from step 3.
After terminating the algorithm, all the numbers that are not marked are prime.
Example
To find all the prime numbers less than or equal to 20, we can create a list of numbers from 2 to 20.
In the above table, we mark all the numbers that are divisible by 2 (shown in red) and are greater than or equal to the square of 2.
After marking all the numbers divisible by 2 and greater than or equal to the square of 2, we move on to the next unmarked prime number, which is 3. We now mark the numbers that are divisible by 3 (shown in blue) and are greater than or equal to the square of 3.
After marking all the numbers divisible by 2, 3, and greater than or equal to the square of those prime numbers, we move on to the next unmarked prime number, which is 5. We now mark the numbers that are divisible by 5 and are greater than or equal to the square of 5. However, in this case, there are no additional numbers to mark as 10, 15, and 20 have already been marked in the previous steps.
In the above table, unmarked numbers are:
Hence, we get the prime numbers (2, 3, 5, 7, 11, 13, 17, and 19).
NthPrimeNumber.java
import java.util.ArrayList;
public class NthPrimeNumber
{
//declare the maximumm size as constant
static int MAX_SIZE = 1000005;
//creating an instance of the ArrayList class that stores all the prime numbers
static ArrayList<Integer> primelist = new ArrayList<Integer>();
//defining a static function to find the nth prime number using Sieve of Eratosthenes approach
static void findnthPrimeNumber()
{
//creating a boolean array and marking all entries as true
//the value IsPrime[i] will be false if i is not a IsPrime
boolean [] IsPrime = new boolean[MAX_SIZE];
for(int i = 0; i < MAX_SIZE; i++)
IsPrime[i] = true;
for (int p = 2; p * p < MAX_SIZE; p++)
{
// If IsPrime[p] is not changed,
// then it is a prime
if (IsPrime[p] == true)
{
//finds the multiples of p greater than or equal to the square of it
//we have already marked the numbers that rae multiple of p and are less than p to the power 2
for (int i = p * p; i < MAX_SIZE; i += p)
IsPrime[i] = false;
}
}
for (int p = 2; p < MAX_SIZE; p++)
if (IsPrime[p] == true)
//adding prime number to the ArrayList
primelist.add(p);
}
// Driver Code
public static void main (String args[])
{
//calling the static function
findnthPrimeNumber();
//get() method returns the specified position in this list
System.out.println("7th prime number is " + primelist.get(6));
System.out.println("22nd prime number is " + primelist.get(21));
System.out.println("10000th prime number is " + primelist.get(9999));
}
}
Output:
7th prime number is 17 22nd prime number is 79 10000th prime number is 104729
Make sure to explore our tutorials.freshersnow.com portal to uncover additional Java concepts akin to nth Prime Number.