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

2021年4月30日19:32:56 发表评论 786 次浏览

## 本文概述

• 使用查找最大质数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 <<endl;
cout <<"16th prime number is " <<primes <<endl;
cout <<"1049th prime number is " <<primes;

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

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

//Driver Code
public static void Main ()
{

//Function call
SieveOfEratosthenes();

Console.WriteLine( "5th prime number is " +
primes);
Console.WriteLine( "16th prime number is " +
primes);
Console.WriteLine( "1049th prime number is " +
primes);
}
}

//This code is contributed by ihritik``````

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