质数筛法

/*
 * 输出第k个质数(质数筛法）
 */
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int MAXN = 1e5;

bool isPrime[MAXN];                 //标记数组
vector<int> prime;                  //保存质数

void initial(){                     //初始化
    fill(isPrime,isPrime+MAXN,true);
    isPrime[0]=false;
    isPrime[1]=false;
    for(int i = 2;i<MAXN;i++){
        if(!isPrime[i]){            //非质数，则跳过该数
            continue;
        }
        prime.push_back(i);
        for(int j = i+i;j<MAXN;j+=i){
            isPrime[j]=false;       //质数的倍数为非质数
        }
    }
    return;
}

int main(){
    initial();
    int k;
    while(scanf("%d",&k)!=EOF){
        printf("%d\n",prime[k-1]);
    }
    return 0;
}