题解 | #Prime Number#

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

//怎么知道要开辟多大空间才能容纳下10000个质数？ 
//一种方法，百度搜索，预先知道是十万多 
//这种方法给人的感觉非常难受！ 

//试一下放弃筛法，寻找当前质因数，会有多慢 

//强的一笔，不是很慢，简单易懂

void Outputkthprime(int k){
	if(k<1 || k>10000){
		printf("Error!\n");
		exit(0);
	}
	if(k==1){
		printf("2\n");
		return;
	}
	vector<int> v;
	v.push_back(2);
	for(int i=3; 1; i++){
		for(int j=0; j<v.size(); j++){
			if(v[j]>sqrt(i)){//发现i幸存，即i是质数
				v.push_back(i); 
				if(v.size()==k){
					printf("%d\n",v[v.size()-1]);
					return;
				}
				break;
			}
			if(i%v[j] == 0){//发现i是合数 
				break;
			}
		}
	}
}

int main(){
	int k;
	while(scanf("%d",&k) != EOF){
		Outputkthprime(k);
	}
	return 0;
}