#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define SpeedUp ios::sync_with_stdio(false)
#define Max (500000)
//#define Debug
using namespace std;

bool p[Max*10];
vector<int> Prime;

void init(){
    for(int i=2;i<=Max;i++){
        if(!p[i]){
            Prime.push_back(i);
            #ifdef Debug
            cout<<i<<endl;
            #endif
        }
        for(int j=0;j<Prime.size();j++){
            int k=i*Prime[j];
            if(k>Max) break;
            p[k]=true;
            if(i%Prime[j]==0) break;
        }
    }
}

void work(){
    int N,k;
    cin>>N;
    while(N--){
        cin>>k;
        cout<<Prime[k-1]<<endl;
    }
}

int main(){
    init();
    work();
    return 0;
}
---------------------------------------------------------------------------
Euler's sieve method.
Could you plz prove it?