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;
System.out.println(num);
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;
}
}

cHVibGljIGNsYXNzIE1haW4gewpwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CmxvbmcgdGltZSA9IFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpOwpmaXJzdFByaW1lcygxMDAwMDAwKTsKU3lzdGVtLm91dC5wcmludGxuKFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpIC0gdGltZSk7Cn0KcHVibGljIHN0YXRpYyBpbnRbXSBmaXJzdFByaW1lcyhpbnQgbikgewppbnRbXSBwcmltZXMgPSBuZXcgaW50W25dOwppbnQgZm91bmQgPSAxOwpwcmltZXNbMF0gPSAyOwppbnQgbnVtID0gMzsKd2hpbGUoZm91bmQgPCBuKSB7CmJvb2xlYW4gcHJpbWUgPSB0cnVlOwpTeXN0ZW0ub3V0LnByaW50bG4obnVtKTsKaW50IHNxcnQgPSAoaW50KSBNYXRoLnNxcnQobnVtKTsKZm9yKGludCBpID0gMTsgaSA8IHByaW1lcy5sZW5ndGggJiYgcHJpbWVzW2ldIDw9IHNxcnQ7IGkrKykgewppZihudW0gJSBwcmltZXNbaV0gPT0gMCkgewpwcmltZSA9IGZhbHNlOwpicmVhazsKfQp9CmlmKHByaW1lKSB7CnByaW1lc1tmb3VuZCsrXSA9IG51bTsKfQpudW0gKz0gMjsKfQpyZXR1cm4gcHJpbWVzOwp9Cn0=