public class Main {
public static void main(String[] args) {
long time = System.currentTimeMillis();
firstPrimes(1000000);
System.out.println(System.currentTimeMillis() - time);
}
public static int[] firstPrimes(int n) {
int[] primes = new int[n];
int found = 1;
primes[0] = 2;
int num = 3;
while(found < n) {
boolean prime = true;
int sqrt = (int) Math.sqrt(num);
for(int i = 1; i < primes.length && primes[i] <= sqrt; i++) {
if(num % primes[i] == 0) {
prime = false;
break;
}
}
if(prime) {
primes[found++] = num;
}
num += 2;
}
return primes;
}
}

cHVibGljIGNsYXNzIE1haW4gewpwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CmxvbmcgdGltZSA9IFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpOwpmaXJzdFByaW1lcygxMDAwMDAwKTsKU3lzdGVtLm91dC5wcmludGxuKFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpIC0gdGltZSk7Cn0KcHVibGljIHN0YXRpYyBpbnRbXSBmaXJzdFByaW1lcyhpbnQgbikgewppbnRbXSBwcmltZXMgPSBuZXcgaW50W25dOwppbnQgZm91bmQgPSAxOwpwcmltZXNbMF0gPSAyOwppbnQgbnVtID0gMzsKd2hpbGUoZm91bmQgPCBuKSB7CmJvb2xlYW4gcHJpbWUgPSB0cnVlOwppbnQgc3FydCA9IChpbnQpIE1hdGguc3FydChudW0pOwpmb3IoaW50IGkgPSAxOyBpIDwgcHJpbWVzLmxlbmd0aCAmJiBwcmltZXNbaV0gPD0gc3FydDsgaSsrKSB7CmlmKG51bSAlIHByaW1lc1tpXSA9PSAwKSB7CnByaW1lID0gZmFsc2U7CmJyZWFrOwp9Cn0KaWYocHJpbWUpIHsKcHJpbWVzW2ZvdW5kKytdID0gbnVtOwp9Cm51bSArPSAyOwp9CnJldHVybiBwcmltZXM7Cn0KfQ==