Spunem că un număr natural este aproape prim dacă el poate fi scris ca produs de două numere prime. De exemplu 6 și 25 sunt aproape prime pentru că 6 = 2 * 3, iar 25 = 5 * 5. Considerăm șirul crescător al numerelor naturale aproape prime: 4, 6, 9, 10, 14, 15, 21, … Acestora li se asociază câte un număr de ordine, numerotarea începând cu 1. Deci 4 este primul număr aproape prim, 6 este al doilea număr, 9 este al treilea etc.

Cerința

Dat un număr natural N, să se determine al N-lea număr aproape prim.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieșire

Programul va afișa pe ecran un singur număr natural, reprezentând al N-lea număr aproape prim.

Restricții și precizări

• 1 ≤ N ≤ 23.378

Exemplul 1:

Intrare

4

Ieșire

10

Exemplul 2:

Intrare

300

Ieșire

1003

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

int E[100001], c, n;
bool e[1000001], B[1000001];
int x = 1000001;

void eratostene(){
    e[0] = e[1] = 1;
    for(int i = 2 ; i * i <= x ; ++i)
        for(int j = 2 ; i * j <= x ; ++j)
            e[i * j] = 1;
    for(int i = 1; i <= 1000000; ++i)
        if(!e[i])
            E[++c] = i;
    for(int i = 1; i < c; ++i)
        for(int j = 1; j <= c; ++j)
            if(1LL * E[i] * E[j] < 1000001)
                B[E[i] * E[j]] = 1;
            else i++, j=1;
    for(int i = 1; n != 0; ++i){
        if(B[i] == 1){
            n--;
            if(n==0){
                cout << i;
                return;
            }
        }
    }
}

int main(){
    cin >> n;
    eratostene();
}