#include <iostream>
#include <vector>
using namespace std;
bool is_prime( int z, vector < int > P )
{
bool ip = true;
for ( int i = 0; P[ i ] * P[ i ] <= z && ip; ++i )
ip = ip && ( z % P[ i ] != 0 );
return ip;
}
int mega_prime( int index )
{
vector < int > MP, P;
P.push_back( 2 );
for ( int x = 3; index > ( int )MP.size(); x += 2 )
{
if ( is_prime( x, P ) )
{
P.push_back( x );
if ( is_prime( ( int )P.size(), P ) )
MP.push_back( x );
}
}
return MP.back();
}
int main()
{
cout << mega_prime( 1 ) << endl;
cout << mega_prime( 2 ) << endl;
cout << mega_prime( 3 ) << endl;
cout << mega_prime( 5 ) << endl;
cout << mega_prime( 10 ) << endl;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpib29sIGlzX3ByaW1lKCBpbnQgeiwgdmVjdG9yIDwgaW50ID4gUCApCnsKICAgIGJvb2wgaXAgPSB0cnVlOwogICAgZm9yICggaW50IGkgPSAwOyBQWyBpIF0gKiBQWyBpIF0gPD0geiAmJiBpcDsgKytpICkKICAgICAgICBpcCA9IGlwICYmICggeiAlIFBbIGkgXSAhPSAwICk7CiAgICByZXR1cm4gaXA7Cn0KIAppbnQgbWVnYV9wcmltZSggaW50IGluZGV4ICkKewogICAgdmVjdG9yIDwgaW50ID4gTVAsIFA7CiAgICBQLnB1c2hfYmFjayggMiApOwogICAgZm9yICggaW50IHggPSAzOyBpbmRleCA+ICggaW50IClNUC5zaXplKCk7IHggKz0gMiApCiAgICB7CiAgICAgICAgaWYgKCBpc19wcmltZSggeCwgUCApICkKICAgICAgICB7CgkgICAgUC5wdXNoX2JhY2soIHggKTsgICAgICAgCiAgICAgICAgICAgIGlmICggaXNfcHJpbWUoICggaW50IClQLnNpemUoKSwgUCApICkKCSAgICAgICAgTVAucHVzaF9iYWNrKCB4ICk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIE1QLmJhY2soKTsKfQogCmludCBtYWluKCkKewogICAgY291dCA8PCBtZWdhX3ByaW1lKCAxICkgPDwgZW5kbDsKICAgIGNvdXQgPDwgbWVnYV9wcmltZSggMiApIDw8IGVuZGw7CiAgICBjb3V0IDw8IG1lZ2FfcHJpbWUoIDMgKSA8PCBlbmRsOwogICAgY291dCA8PCBtZWdhX3ByaW1lKCA1ICkgPDwgZW5kbDsKICAgIGNvdXQgPDwgbWVnYV9wcmltZSggMTAgKSA8PCBlbmRsOwp9