You do not have to track sieve for even numbers. Keeping info only for odd numbers will decrease the number of operations twice, as well as the memory size, that may be even more important.
You can use int bit array instead of boolean for sieve, so each element will require 1 bit instead of 1 byte. It looks like a bit more of processor work, but decrease memory usage 8 more times, that is more important since the memory latency seems to be the bottleneck in this problem.
And, yes, you can start filling the sieve from j*j instead of 2*j, and when j*j becomes >= SIEVE_LEN, you can stop sieving and simply collect all the remaining primes.
Update: for me, the most important problem here was fast input and output.
My sieve version works in 0.36 seconds at ideone, input is hand-made and output if kind of “buffered”, so the problem is accepted in 0.48 seconds.
The main loop looks like:
InputStream in = System.in;
int t = readUint(in);
StringBuilder sb = new StringBuilder();
for (int it = 0; it < t; it++) {
int n = readUint(in);
sb.append(primes[n - 1]);
sb.append('\n');
}
System.out.print(sb.toString());
and readUint function looks like:
public static int readUint(InputStream in) throws java.io.IOException
{
int u = 0;
for(;;) {
int c = in.read();
assert (0 <= c);
u = c - 48;
if (0 <= u && u < 10)
break;
}
for (;;) {
int v = in.read() - 48;
if (0 > v || v >= 10)
break;
u = u * 10 + v;
}
return u;
}
Probably, a hand-made version of output (in bytes, without chars) could save some milliseconds.
Creating a BufferedInputStream around System.in increased runtime to 0.52s, so System.in looks already buffered.