算法题(查找第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#
//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

    推荐阅读