Given an integer N. The task is to find the Nth prime number.
Examples:
Input : 5
Output : 11Input : 16
Output : 53Input : 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 Eratosthenesvoid 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 Codeint 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 codeif __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 numbersstatic ArrayList primes = new ArrayList();// Function to generate N prime numbers using // Sieve of Eratosthenesstatic 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 Codepublic 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 valuevar MAX_SIZE = 1000005;// Function to generate N prime numbers using// Sieve of Eratosthenesfunction 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 primesint 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 nint 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 numberimport 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 primesdef 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 ndef 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 codeprint("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 numberusing 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 primesfunction 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 nfunction 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 codeconsole.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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
