# Find nth prime number in Java – Explained with Examples

In this Java tutorial, we will learn- How to Find nth prime number in Java? As we’ve already learned in our previous tutorial- How to develop a Java program to find Prime numbers within a given range. This time just for a given input- ## What are the Prime Numbers

In simple words, Prime numbers are basically some natural numbers that are greater than 1 and are can only be divided by 1 and themselves.

For example, 11 is a prime number because it can only be divided by only 1 and 11.

However, 12 is not a prime number because it can be divided by 2, 3, 4, 6 and itself.

Now, we know what are the prime numbers, now let’s understand- How to Find nth Prime number in Java?

## Find nth Prime Number in Java – Step by Step

Now you know, What are Prime numbers and how they are different from other numbers. Probably, it’s one of the main reasons that, you will face Java interviews where they will ask you to write a Program to find nth prime number in Java.

Btw, here I’ve already shared a great collection of 51+ Java Interview Questions and Answers with detailed explanations, so can learn and understand a number of Java based Programming Questions in one place.

Now, let’s see a program to find nth Prime number in Java-

```package com.shubhamklogic.java.tutorials;                                              // Steps:

public class NthPrimeNumberFinder                                                        // Defining the Java class
{
public static void main( String[] args )
{
int usersNumber = 5;                                                                                // Finding 5th Prime number...

// Verifying the time taken with this approach
long timeStart = System.currentTimeMillis();

System.out.println( "Prime Number at "+ usersNumber +"th position = "
+ findNthPrimeNormally( usersNumber ));

long timeEnd = System.currentTimeMillis(); float sec = (timeEnd - timeStart) / 1000F;
System.out.println("[INFO] Time taken with this approach: "+sec+" Seconds\n");
}

public static int findNthPrimeNormally(int num)                             // Method to find Prime Num. at given position num.
{
int positionCounter = 0;

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

positionCounter++;                                                                         // Incrementing the counter, whenever found a Prime number

if(positionCounter == num) {                                                          // Returning the Prime number at desired position
return i;
}
}
}

private static boolean isPrimeNumber(long num)                         // Simple method to validate a Prime number
{
if(num < 2)
return false;

for (long i = 2; i * i <= num; i++) {
if (num % i == 0)
return false;
}
return true;
}
}
```

Output: Once you’ll run the above Java program, you’ll get the following output-

```Prime Number at 5th position = 11
[INFO] Time taken with this approach: 0.001 Seconds```

## Logic – Behind the Code

The above solution to Find nth Prime number gave the correct results. Here are the steps, How we did that-

[Step 1] We have taken a number 5 as a User input.

[Step 2] Passed that number to our method findNthPrimeNormally(…)

[Step 3] Inside the findNthPrimeNormally(…) method, we set the counter to Zero 0, and found the Prime number at 5th position with the help of our isPrimeNumber(…) method.

[Step 4] In the method isPrimeNumber(…), we applied the basic rules to verify whether it’s a Prime number or not. If it’s a prime number, return true otherwise false.

[Optional Step] If you’ve observed the solution carefully, then you’ve noticed that we had implemented the solution in such a way that gives us results with Total time taken by the method findNthPrimeNormally(…)

Most of you might think that’s a perfect solution, which successfully finds nth Prime number with less than half of a second, then wait and have a look at the below Test results

```INPUT:      int usersNumber = 5000;
OUTPUT:     Prime Nunmber at 5000 position = 48611
[INFO] Time Taken with a Simple approach: 0.034 Seconds

INPUT:      int usersNumber = 50000;
OUTPUT:     Prime Nunmber at 50000 position = 611953
[INFO] Time Taken with a Simple approach: 0.539 Seconds

INPUT:      int usersNumber = 500000;
OUTPUT:     Prime Nunmber at 500000 position = 7368787
[INFO] Time Taken with a Simple approach: 18.5 Seconds

And If you want to find Prime number at 1 millionth position, then you might have to wait for atleast 1 minutes-

INPUT:      int usersNumber = 1000000;
OUTPUT:     Prime Nunmber at 1000000 position = 15485863
[INFO] Time Taken with a Simple approach: 56.791 Seconds

... and so on ...```

After looking at the above Test results, think about a scenario, when your Java application needs to find a Prime number at 30 millionth position, then you might have to wait for half an hour with the above solution, which will definitely not be acceptable.

So, in such cases, you need an efficient algorithm using which you can find nth Prime number in a fraction of time. Here is an efficient and one of the fastest solution to Find nth Prime number in Java-

## Find the nth Prime number in Fastest possible way

As we know, if the number is divided by any other number instead of 1 and itself, that’ll not consider as a Prime number. An important fact about the divisors is that- Divisors come in pairs.

If we take n=6 as an example, then one of its divisors is 2, while the other one is n/2 <=> 6/2 <=> 3. Here the pair of divisors of 6 is (2,3).

Another important fact is, If n is composite, its smallest nontrivial divisor does not exceed √n.

Since there are squares of primes and products of two close primes, like 323 = 17*19, we cannot reduce the limit for the trial division loop below √n. Therefore, we must look for other ways to improve the algorithm now.

So, Instead of investigating the numbers one by one and checking whether each is prime from scratch, you can also consider a group of relevant numbers as one piece and eliminate the multiples of a given prime in one go. This algorithm is best known as the Sieve of Eratosthenes:

When using this algorithm, you need to find the prime numbers not exceeding N. You can break down this algorithm into 2 Sub-steps:

Step 1} Make a list of all numbers from 2 to N,

Step 2} For each k from 2 to N: if k is not yet crossed off, it is prime; cross off all multiples of k as composites.

And we’ll have all the numbers in the list which aren’t crossed off.

(Btw, if you don’t know what does Sieve means? It simply means Filtration- To filter garbage items for purifying something).

In this algorithm, What matters the most is finding the upper limit to where we need to search for the divisors. And for that, It follows p(n) ~ n*log n, where p(n) is the nth prime, and there are good upper bounds for p(n) known from deeper analysis. The formula is like:-

n*(log n + log (log n) – 1) < p(n) < n*(log n + log (log n)), for n >= 6

So we can use the above expression to calculate the sieving or filtering limit, as it doesn’t exceed the target far.

Before implementing the above algorithm, there are some easy improvements on the basic algorithm, that are:

• Start crossing off multiples of p only at , not at 2*p
• We can eliminate the even numbers from the sieve.

Btw, none of these improvements would reduce the algorithmic complexity, but they all reduce the thorny constant factors by a significant amount.

### The Solution :

```package com.shubhamklogic.java.tutorials;

public class NthPrimeNumberFinder                                       // Defining a class...
{
public static void main( String[] args )
{
int n = 5;                                                      // Higher Input: 5000, 500000, 5000000...
long timeStart = System.currentTimeMillis();

System.out.println( n+"th Prime Number = "+
findNthPrimeEfficiently(n) );               // Invoking the method...

long timeEnd = System.currentTimeMillis();float sec = (timeEnd - timeStart) / 1000F;

System.out.println("[INFO] Time taken with this approach: "+sec+" Seconds\n");
}

public static int findNthPrimeEfficiently(int n) {

if (n < 2) return 2;                                                     // Simple Returns...
if (n == 2) return 3;

int range, root, count = 1;

// Setting the upper range...
range = (int)( n*(Math.log(n) + Math.log(Math.log(n))) ) + 3;

root = (int)Math.sqrt(range) + 1;                      // Getting the square root of the range...
range = (range-1)/2;
root = root/2 - 1;

boolean[] sieve = new boolean[range];                  // Array to store Results...
for(int i = 0; i < root; ++i) {

if (!sieve[i]) {
++count;

for(int j = 2*i*(i+3)+3, p = 2*i+3; j < range; j += p) {
sieve[j] = true;
}
}
}

int p;
for(p = root; count < n; ++p) {
if (!sieve[p]) {
++count;                                                                 // Incrementing counter until it reachs till the number
}
}
return 2*p+1;                                                               // Returning the Prime number at nth position
}
}```

Output : When you’ll run the above Java program, you’ll successfully get the following output-

```5th Prime Number = 11
[INFO] Time Taken with this approach: 0.0 Seconds```

## Checking the Robustness and Performance

Let’s have a look at the performance of above nth Prime Number Algorithm and program with Higher Inputs Values-

```Input : 5000
Output: 5000th Prime Number = 48611
[INFO] Time Taken with this approach: 0.003 Seconds

Input : 500000
Output: 500000th Prime Number = 7368787
[INFO] Time Taken with this approach: 0.077 Seconds

Input : 5000000
Output: 5000000th Prime Number = 86028121
[INFO] Time Taken with this approach: 0.851 Seconds

Input : 10000000 ( 10 Million == 1 Crore )
Output: 10000000th Prime Number = 179424673
[INFO] Time Taken with this approach: 1.498 Seconds
```

## Wrap Up

In this Java tutorial, we have learned- What are the Prime numbers? How to write a simple program to Find nth Prime Number using Java with complete explanation and sample Inputs-Outputs. We have also understood and implemented the algorithm of Sieve of Eratosthenes and tried to Find the nth Prime number in Fastest possible way.

I hope this article helped you and now you understand How to develop a Java program to find Prime numbers. Don’t forget to check other related Java articles that you may like: