public class Primes {
	int MAX_PRIME     =   999983; // exe: 0.029s   mem: 500 KB
	int PRIMES_LENGTH =    78498;
//	int MAX_PRIME     =  9999991; // exe: 0.213s   mem: 4 MB
//	int PRIMES_LENGTH =   664579;
//	int MAX_PRIME     = 49999991; // exe: 1.404s   mem: 16 MB
//	int PRIMES_LENGTH =  3001134;
	int MAX_BITS = MAX_PRIME/2 + 1;
	int[] primes = new int[PRIMES_LENGTH];
	java.util.BitSet composite = new java.util.BitSet(MAX_BITS);
	
	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.get(++b));
		}
		for (int b=1, i=1; i < PRIMES_LENGTH; b++)
			if (!composite.get(b)) primes[i++] = b+b+1;
	}

}