SPOJ Finding the Kth Prime

// Header file begin


#include<iostream>


#include<cstdio>


#include<cstring>


#include<map>


#include<string>


#include<vector>


#include<cmath>


#include<cctype>


#include<sstream>


#include<set>


#include<list>


#include<stack>


#include<utility>


#include<queue>


#include<algorithm>


#include<cstdlib>


#include<bitset>


// End


//..........


// Macro


#define sf scanf


#define pf printf


#define lp1(i,n) for(i=0;i<n;i++)


#define lp2(i,n) for(i=1;i<=n;i++)


#define mset(c,v) memset(c,v,sizeof(c))


#define outs(a) cout<<" "<<a<<" "


#define nl puts("")


#define sq(x) ((x)*(x))


#define all(x) x.begin(),x.end()


#define reall(x) x.rbegin(),x.rend()


#define s_wap(x,y) x^=y;y^=x;x^=y;


#define sz size()


#define gc getchar()


#define psb push_back


#define freader freopen("input.txt","r",stdin)


// End.........


 


// Size


#define mx7 87000000


#define mx6 1500000


#define mx5 100005


#define mx4 10001000


#define inf 1<<30                                           //infinity value


#define eps 1e-9


#define mx (65540)


#define mod 1000000007


#define pi acos(-1.0)


 


// Macros for Graph


 


#define white 1


#define gray 2


#define black 3


#define nil 0


 


using namespace std;


 


typedef long long LL;


 


 


LL prime[(mx7>>6)+1], prm[(mx7>>1)+9], plen=1;


 


#define setbit(n) (prime[n>>6] |= (1 << ((n >> 1)&31)))


#define checkbit(n) (prime[n>>6] & (1 << ((n >> 1)&31)))


 


void sieve()


{


    LL i,j;


 


    for(i=3; i*i<=mx7; i+=2)


    {


        if(!checkbit(i))


        {


            for(j=i*i; j<=mx7; j+=(2*i))


            {


                setbit(j);


            }


        }


    }


 


    prm[plen++] = 2;


 


    for(i=3; i<=mx7; i+=2)


    {


        if(!checkbit(i))


        {


            prm[plen++] = i;


        }


    }


 


   // cout << plen;


 


    //for(i=1; i<=plen; i++) cout << prm[i] << " ";


}


 


int main()


{


    sieve();


    LL q;


    sf("%lld", &q);


    while(q--)


    {


        LL k;


        sf("%lld", &k);


        pf("%lld\n", prm[k]);


    }


 


    return 0;


}