Program to find the Nth Prime Number

Namachila 3 weeks ago

0 0 10 minutes read

Given an integer N. The task is to find the Nth prime number.

Examples:

Input : 5
Output : 11

Input : 16
Output : 53

Input : 1049
Output : 8377

Approach:

Find the prime numbers up to MAX_SIZE using Sieve of Eratosthenes.
Store all primes in a vector.
For a given number N, return the element at (N-1)th index in a vector.

Below is the implementation of the above approach:

C++

// C++ program to the nth prime number
 
#include <bits/stdc++.h>
using namespace std;
 
// initializing the max value
#define MAX_SIZE 1000005
 
// Function to generate N prime numbers using
// Sieve of Eratosthenes
void SieveOfEratosthenes(vector<int>& primes)
{
    // Create a boolean array "IsPrime[0..MAX_SIZE]" and
    // initialize all entries it as true. A value in
    // IsPrime[i] will finally be false if i is
    // Not a IsPrime, else true.
    bool IsPrime[MAX_SIZE];
    memset(IsPrime, true, sizeof(IsPrime));
 
    for (int p = 2; p * p < MAX_SIZE; p++) {
        // If IsPrime[p] is not changed, then it is a prime
        if (IsPrime[p] == true) {
            // Update all multiples of p greater than or
            // equal to the square of it
            // numbers which are multiple of p and are
            // less than p^2 are already been marked.
            for (int i = p * p; i < MAX_SIZE; i += p)
                IsPrime[i] = false;
        }
    }
 
    // Store all prime numbers
    for (int p = 2; p < MAX_SIZE; p++)
        if (IsPrime[p])
            primes.push_back(p);
}
 
// Driver Code
int main()
{
    // To store all prime numbers
    vector<int> primes;
 
    // Function call
    SieveOfEratosthenes(primes);
 
    cout << "5th prime number is " << primes[4] << endl;
    cout << "16th prime number is " << primes[15] << endl;
    cout << "1049th prime number is " << primes[1048];
 
    return 0;
}

Java

// Java program to the nth prime number  
import java.util.ArrayList;
class GFG
{
     
    // initializing the max value 
    static int MAX_SIZE = 1000005;
     
    // To store all prime numbers
    static ArrayList<Integer> primes =
       new ArrayList<Integer>();
     
    // Function to generate N prime numbers 
    // using Sieve of Eratosthenes
    static void SieveOfEratosthenes() 
    { 
        // Create a boolean array "IsPrime[0..MAX_SIZE]" 
        // and initialize all entries it as true. 
        // A value in IsPrime[i] will finally be false 
        // if i is Not a IsPrime, else true. 
        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) 
            { 
                // Update all multiples of p greater than or 
                // equal to the square of it 
                // numbers which are multiple of p and are 
                // less than p^2 are already been marked. 
                for (int i = p * p; i < MAX_SIZE; i += p) 
                    IsPrime[i] = false; 
            } 
        } 
     
        // Store all prime numbers 
        for (int p = 2; p < MAX_SIZE; p++) 
        if (IsPrime[p] == true) 
                primes.add(p);
    } 
     
    // Driver Code
    public static void main (String[] args) 
    {
         
        // Function call
        SieveOfEratosthenes();
     
        System.out.println("5th prime number is " + 
                                    primes.get(4));
        System.out.println("16th prime number is " + 
                                    primes.get(15));
        System.out.println("1049th prime number is " + 
                                    primes.get(1048));
    }
}
 
// This code is contributed by ihritik

Python3

# Python3 program to the nth prime number  
primes = []
 
# Function to generate N prime numbers using  
# Sieve of Eratosthenes 
def SieveOfEratosthenes():
     
    n = 1000005
     
    # Create a boolean array "prime[0..n]" and 
    # initialize all entries it as true. A value
    # in prime[i] will finally be false if i is 
    # Not a prime, else true. 
    prime = [True for i in range(n + 1)] 
     
    p = 2
    while (p * p <= n): 
           
        # If prime[p] is not changed, 
        # then it is a prime 
        if (prime[p] == True): 
               
            # Update all multiples of p 
            for i in range(p * p, n + 1, p): 
                prime[i] = False
                 
        p += 1
       
    # Print all prime numbers 
    for p in range(2, n + 1): 
        if prime[p]: 
            primes.append(p) 
   
# Driver code
if __name__=='__main__': 
     
    # Function call 
    SieveOfEratosthenes()
     
    print("5th prime number is", primes[4]); 
    print("16th prime number is", primes[15]); 
    print("1049th prime number is", primes[1048]); 
     
# This code is contributed by grand_master

C#

// C# program to the nth prime number 
using System;
using System.Collections;
 
class GFG
{
     
// initializing the max value 
static int MAX_SIZE = 1000005;
 
// To store all prime numbers
static ArrayList primes = new ArrayList();
 
// Function to generate N prime numbers using 
// Sieve of Eratosthenes
static void SieveOfEratosthenes() 
{ 
    // Create a boolean array "IsPrime[0..MAX_SIZE]" 
    // and initialize all entries it as true. 
    // A value in IsPrime[i] will finally be false
    // if i is Not a IsPrime, else true. 
    bool [] IsPrime = new bool[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) 
        { 
            // Update all multiples of p greater than or 
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked. 
            for (int i = p * p; i < MAX_SIZE; i += p) 
                IsPrime[i] = false; 
        } 
    } 
 
    // Store all prime numbers 
    for (int p = 2; p < MAX_SIZE; p++) 
    if (IsPrime[p] == true) 
            primes.Add(p);
} 
 
// Driver Code
public static void Main () 
{
     
    // Function call
    SieveOfEratosthenes();
 
    Console.WriteLine("5th prime number is " + 
                                   primes[4]);
    Console.WriteLine("16th prime number is " +
                                   primes[15]);
    Console.WriteLine("1049th prime number is " +
                                   primes[1048]);
}
}
 
// This code is contributed by ihritik

Javascript

<script>
 
// Javascript program to the nth prime number
 
// initializing the max value
var MAX_SIZE = 1000005;
 
// Function to generate N prime numbers using
// Sieve of Eratosthenes
function SieveOfEratosthenes(primes)
{
    // Create a boolean array 
    // "IsPrime[0..MAX_SIZE]" and
    // initialize all entries it as true. 
    // A value in
    // IsPrime[i] will finally be false if i is
    // Not a IsPrime, else true.
    var IsPrime = Array(MAX_SIZE).fill(true);
     
    var p,i;
    for (p = 2; p * p < MAX_SIZE;p++)
    {
        // If IsPrime[p] is not changed, 
        // then it is a prime
        if (IsPrime[p] == true) 
        {
            // Update all multiples of p 
            // greater than or
            // equal to the square of it
            // numbers which are multiple
            // of p and are
            // less than p^2 are already 
            // been marked.
            for(i = p * p; i < MAX_SIZE; i += p)
                IsPrime[i] = false;
        }
    }
 
    // Store all prime numbers
    for (p = 2; p < MAX_SIZE; p++)
        if (IsPrime[p])
            primes.push(p);
}
 
// Driver Code
    // To store all prime numbers
    var primes = [];
 
    // Function call
    SieveOfEratosthenes(primes);
 
    document.write(
    "5th prime number is "+primes[4]+"<br>"
    );
    document.write(
    "16th prime number is "+primes[15]+"<br>"
    );
    document.write(
    "1049th prime number is "+primes[1048]+"<br>"
    );
 
</script>

Output

5th prime number is 11
16th prime number is 53
1049th prime number is 8377

Another approach :

for finding prime number at given position write a isPrime function to check number is prime or not
write a function to get prime number at given position

Below is the implementation of the above approach :

C++

// c++ program to find the n-th prime number
 
#include <bits/stdc++.h>
using namespace std;
 
 
// function to check given number is prime or not
// basic idea is numbers not divided by any primes are primes
int isPrime(int k)
{
    // Corner cases
    if (k <= 1)
        return 0;
    if (k==2 || k==3)
        return 1;
  
    // below 5 there is only two prime numbers 2 and 3 
    if (k % 2 == 0 || k % 3 == 0)
        return 0;
  
  // Using concept of prime number can be represented in form of (6*k + 1) or(6*k - 1) 
    for (int i = 5; i * i <= k; i = i + 6)
        if (k % i == 0 || k % (i + 2) == 0)
            return 0;
  
    return 1;
}
 
 
// function which gives prime at position n
int nThPrime(int n)
{
    int i=2;
     
    while(n>0)
    {
        // each time if a prime number found decrease n
        if(isPrime(i))
          n--;
        
        i++;  //increase the integer to go ahead
    }
    i-=1; // since decrement of k is being done before 
          //Increment of i , so i should be decreased by 1
    return i;
}
 
int main() 
{
    cout<<"5th prime number is : "<<nThPrime(5)<<"\n";
    cout<<"7th prime number is : "<<nThPrime(7)<<"\n";
    cout<<"10th prime number is : "<<nThPrime(10)<<"\n";
    return 0;
}
// This code is contributed by Ujjwal Kumar Bhardwaj

Java

// Java program to find the n-th prime number
import java.util.*;
class GFG {
 
  // function to check given number is prime or not
  // basic idea is numbers not divided by any primes are
  // primes
  static int isPrime(int k)
  {
 
    // Corner cases
    if (k <= 1)
      return 0;
    if (k == 2 || k == 3)
      return 1;
 
    // below 5 there is only two prime numbers 2 and 3
    if (k % 2 == 0 || k % 3 == 0)
      return 0;
 
    // Using concept of prime number can be represented
    // in form of (6*k + 1) or(6*k - 1)
    for (int i = 5; i * i <= k; i = i + 6)
      if (k % i == 0 || k % (i + 2) == 0)
        return 0;
 
    return 1;
  }
 
  // function which gives prime at position n
  static int nThPrime(int n)
  {
    int i = 2;
 
    while (n > 0) 
    {
 
      // each time if a prime number found decrease n
      if (isPrime(i) == 1)
        n--;
 
      i++; // increase the integer to go ahead
    }
    i -= 1; // since decrement of k is being done before
    // Increment of i , so i should be decreased
    // by 1
    return i;
  }
 
  public static void main(String[] args)
  {
    System.out.println("5th prime number is : "
                       + nThPrime(5));
    System.out.println("7th prime number is : "
                       + nThPrime(7));
    System.out.println("10th prime number is : "
                       + nThPrime(10));
  }
}
 
// This code is contributed by phasing17

Python3

# Python3 program to find the n-th prime number
 
# function to check given number is prime or not
# basic idea is numbers not divided by any primes are primes
def isPrime(k):
 
    # Corner cases
    if (k <= 1):
        return 0
    if (k == 2 or k == 3):
        return 1
 
    # below 5 there is only two prime numbers 2 and 3
    if (k % 2 == 0 or k % 3 == 0):
        return 0
 
  # Using concept of prime number can be represented in form of (6*k + 1) or(6*k - 1)
    for i in range(5, 1 + int(k ** 0.5), 6):
        if (k % i == 0 or k % (i + 2) == 0):
            return 0
 
    return 1
 
# function which gives prime at position n
def nThPrime(n):
    i = 2
    while(n > 0):
 
        # each time if a prime number found decrease n
        if(isPrime(i)):
            n -= 1
 
        i += 1  # increase the integer to go ahead
 
    i -= 1  # since decrement of k is being done before
    # Increment of i , so i should be decreased by 1
    return i
 
# Driver code
print("5th prime number is :", nThPrime(5))
print("7th prime number is :", nThPrime(7))
print("10th prime number is :", nThPrime(10))
 
# This code is contributed by phasing17

C#

// C# program to find the n-th prime number
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // function to check given number is prime or not
  // basic idea is numbers not divided by any primes are
  // primes
  static int isPrime(int k)
  {
    // Corner cases
    if (k <= 1)
      return 0;
    if (k == 2 || k == 3)
      return 1;
 
    // below 5 there is only two prime numbers 2 and 3
    if (k % 2 == 0 || k % 3 == 0)
      return 0;
 
    // Using concept of prime number can be represented
    // in form of (6*k + 1) or(6*k - 1)
    for (int i = 5; i * i <= k; i = i + 6)
      if (k % i == 0 || k % (i + 2) == 0)
        return 0;
 
    return 1;
  }
 
  // function which gives prime at position n
  static int nThPrime(int n)
  {
    int i = 2;
 
    while (n > 0) {
      // each time if a prime number found decrease n
      if (isPrime(i) == 1)
        n--;
 
      i++; // increase the integer to go ahead
    }
    i -= 1; // since decrement of k is being done before
    // Increment of i , so i should be decreased
    // by 1
    return i;
  }
 
  public static void Main(string[] args)
  {
    Console.WriteLine("5th prime number is : "
                      + nThPrime(5));
    Console.WriteLine("7th prime number is : "
                      + nThPrime(7));
    Console.WriteLine("10th prime number is : "
                      + nThPrime(10));
  }
}
 
// This code is contributed by phasing17

Javascript

// JS program to find the n-th prime number
 
 
// function to check given number is prime or not
// basic idea is numbers not divided by any primes are primes
function isPrime(k)
{
    // Corner cases
    if (k <= 1)
        return 0;
    if (k==2 || k==3)
        return 1;
  
    // below 5 there is only two prime numbers 2 and 3 
    if (k % 2 == 0 || k % 3 == 0)
        return 0;
  
  // Using concept of prime number can be represented in form of (6*k + 1) or(6*k - 1) 
    for (let i = 5; i * i <= k; i = i + 6)
        if (k % i == 0 || k % (i + 2) == 0)
            return 0;
  
    return 1;
}
 
 
// function which gives prime at position n
function nThPrime(n)
{
    let i=2;
     
    while(n>0)
    {
        // each time if a prime number found decrease n
        if(isPrime(i))
          n--;
        
        i++;  //increase the integer to go ahead
    }
    i-=1; // since decrement of k is being done before 
          //Increment of i , so i should be decreased by 1
    return i;
}
 
 
// Driver code
console.log("5th prime number is : "+nThPrime(5));
console.log("7th prime number is : "+nThPrime(7));
console.log("10th prime number is : "+nThPrime(10));
 
 
// This code is contributed by phasing17

Output

5th prime number is : 11
7th prime number is : 17
10th prime number is : 29

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!