1086
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <list>
 
using namespace std;
 
const int N = 170000;
 
bool isPrime[N/2+1]; // isPrime[0] corresponds to 1
                     // isPrime[1] corresponds to 3 
                     // etc
                     // ...
                     // isPrime[x/2] corresponds to x (x must be odd)
 
int m[20000];
 
int main()
{
    #ifdef ALEX
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
//    freopen(INPUT_FILE, "r", stdin);
//    freopen(OUTPUT_FILE, "w", stdout);
#endif
    // init
    isPrime[0]=false;
    for(int i=1; i<=N/2; i++) isPrime[i]=true;
 
    // for each odd prime
    for(int i=1; i<=N/2; i++)
    {
        if (isPrime[i])
        {
            int step  = i*2+1;
            int start = 2*i*(i+1); 
 
            if (start>N/2) break; // only primes left in the sieve
 
            for(int j=start; j<=N/2; j+=step) isPrime[j]=false;
        }
    }
 
    int c = 1;
    m[0] = 2;
    for (int i = 1; i <= N; i+=2)
    {
        if (isPrime[i/2])
        {
            m[c] = i;
            c++;
        }
    }
    //printf("count = %d\n", c);
 
    int k;
    cin >> k;
    for(int i = 0; i < k; i++)
    {
        int n;
        cin >> n;
        cout << m[n-1] << endl;
    }
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.