PrimesWithRequests

// Вывод простых чисел в диапазоне от 1 до n.
#include <iostream>
#include <assert.h>
using std::cin;
using std::cout;

// Массив целых чисел фиксированной длины.
// При использовании необходимо гарантировать, что размер Body совпадает с Size.
struct CArray {
    int* Body;
    int Size;

    CArray() : Body( 0 ), Size( 0 ) {}
    ~CArray() { delete[] Body; }
};

// Возвращает простые числа в диапазоне от 1 до n включительно.
void GetPrimes( int n, CArray& primes )
{
    // Выделяем массив под решето.
    bool* sieve = new bool[n + 1];
    for( int i = 0; i <= n; ++i ) {
        sieve[i] = true;
    }
    sieve[0] = sieve[1] = false;

    int primesCount = 0; // Количество простых.
    for( int i = 2; i <= n; ++i ) {
        if( sieve[i] ) {
            // Выкалываем кратные.
            for( int k = 2 * i; k <= n; k += i ) {
                sieve[k] = false;
            }
            ++primesCount;
        }
    }

    primes.Size = primesCount;
    primes.Body = new int[primesCount];
    int k = 0;
    for( int i = 2; i <= n; ++i ) {
        if( sieve[i] ) {
            primes.Body[k++] = i;
        }
    }

    delete[] sieve;
}

int main()
{
    int n = 0;
    cin >> n;

    CArray primes;
    GetPrimes( n, primes );

    int requestsCount = 0;
    cin >> requestsCount;

    for( int i = 0; i < requestsCount; ++i ) {
        int primeIndex = 0;
        cin >> primeIndex;
        assert( primeIndex < primes.Size );
        cout << primes.Body[primeIndex] << std::endl;
    }

    return 0;
}