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

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

本文概述

给定一个整数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

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: