Timus online judg 1086. Cryptography

Problem Link

Solution in c++


#include <iostream>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;

typedef long long ll;

#define sc1(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%lld %lld",&a,&b)

#define pf1(a) printf("%lld\n",a)
#define pf2(a,b) printf("%lld %lld\n",a,b)

#define mx 1000007
#define mod 10000007
#define Accepted 0

int mark[mx], nprime;

vector <int> primeNumbers;
void sieve()
{
    bool prime[mx];

    memset(prime, true, sizeof(prime));

    for (int p = 2; p*p <= mx; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=mx; i += p)
                prime[i] = false;
        }
    }

    for (int p=2; p<=mx; p++)
       if (prime[p])
          primeNumbers.push_back(p);
}


int main()
{
    sieve();
    int num;
    cin >> num;

    while(num--)
    {
        int pos;
        cin >> pos;

        cout << primeNumbers[pos-1] << endl;
    }

    return Accepted;
}