HUSTOJ 1946: Prime Number

题目描述

Output the k-th prime number.

输入

k≤10000

输出

The k-th prime number.

样例输入

10
50

样例输出

29
229

解题思路

  1. 获取素数使用素数筛法,见HUSTOJ 1945
  2. 无法直观获取第10e4个素数,maxn可以先设置一个较大的数,将pnum和10e4比较

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;

const int maxn=104730;
int pnum=0;
int prime[maxn]={0};
bool p[maxn]={0}; // 0 is prime;

void getprime()
{
for(int i=2; i<maxn; i++)
{
if(!p[i])
{
prime[pnum++]=i;
}
for(int j=i+i; j<maxn; j=j+i)
{
p[j]=1;
}
}

}

int main()
{
int k=0;
getprime();
while(cin>>k)
{
cout<<prime[k-1]<<endl;
}
return 0;
}
分享到: