#include <bitset>

const int MAX_PRIME     =   999983; // exe: 0.005s   mem: 377 KB
const int PRIMES_LENGTH =    78498;
/*
const int MAX_PRIME     =  9999991; // exe: 0.045s   mem: 3.3 MB
const int PRIMES_LENGTH =   664579;
const int MAX_PRIME     = 99999989; // exe: 1.438s   mem: 29.3 MB
const int PRIMES_LENGTH =  5761455;
*/
const int MAX_BITS = MAX_PRIME/2 + 1;

int primes[PRIMES_LENGTH];
bitset<MAX_BITS> composite;

void genPrimes() {
	primes[0] = 2;
	for (int b=1, p=3, x=9; x < MAX_PRIME; p = b+b+1, x = p*p) {
		for (x >>= 1; x < MAX_BITS; x += p) composite.set(x);
		while (composite.test(++b));
	}
	for (int b=1, i=1; b < MAX_BITS; b++)
		if (!composite.test(b)) primes[i++] = b+b+1;
}