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++) {
            
            if( isPrimeNumber(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:

Source: Wikipedia

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
    }
}

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

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