本文概述
- C ++
- Java
- C#
例子:
输入: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
推荐阅读
- 算法设计(迭代后序遍历|S2(使用栈stack))
- 算法题(硬币游戏赢家,每个玩家都有三个选择)
- 算法题(查找第N个谐波数的程序)
- 瑞士信贷技术分析师面试
- PHP上传进度条实现详细示例
- 重新排列数组,使索引相同的子集的总和与原始数组中的总和不同
- 按照数组中出现元素的顺序对链表进行排序
- 硬实时和软实时系统之间有什么区别()
- 算法题(最大的按行和按列排序的子矩阵)