题解 | #Prime Number#

#include<iostream>
#include<math.h>
#include<vector>

using namespace std;

const int MAXN = 1e6;

bool isPrime[MAXN];    //辅助数组

vector<int> prime;   //定义向量，存放质数

void Initial(){
	for(int i = 0; i < MAXN; ++i){
		isPrime[i] = true;     //默认将区间内的所有数都初始化为质数
	}
	isPrime[0] = false;
	isPrime[1] = false;
	for(int i = 2; i < MAXN; ++i) {
		if(!isPrime[i]) {    //非质数直接跳过
			continue;
		}
		prime.push_back(i);    //质数入向量
		if(i > MAXN / i) {
			continue;
		}
		for(int j = i * i; j < MAXN; j += i) {    //质数的倍数是非质数
			isPrime[j] = false;
		}
	}		
}

int main() {
	int k;  
	while(scanf("%d",&k) != EOF){
		Initial();
		printf("%d\n",prime[k-1]);  //直接输出第k个质数即可,这里注意以下下标与位序的关系
	}
	return 0;
}