算法题：查找第N个素数的程序

本文概述

• C ++
• Java
• C#

给定一个整数N。任务是找到第N个质数。

例子：

输入：5
输出：11
输入：16
输出：53
输入：1049
输出：8377

方法：

• 使用查找最大质数MAX_SIZEEratosthenes筛.
• 将所有素数存储在向量中。
• 对于给定的数字N, 返回向量中第(N-1)个索引处的元素。

下面是上述方法的实现：

C ++

//CPP 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
 is not changed, then it is a prime 
         if (IsPrime
 == 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
) 
             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
 is not changed, //then it is a prime 
             if (IsPrime
 == 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
 == 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

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




 is not changed, //then it is a prime 
         if (IsPrime
 == 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
 == 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

输出如下：

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

---