算法题（查找第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 【算法题（查找第N个素数的程序）】 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# 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

输出如下：