Print first 100000 Prime numbers in Java

Question

I was trying to build a simple program in Java to print the first N prime numbers.

Here is my program, it's working fine up to input N=10000, but if we increase the input to N=100000, it goes into a continuous loop and takes a lot of time. I tried to optimize it more so that it can work fine for the input N=100000, but no luck far. Could you please suggest if we can optimize the code so that it will work fine for the larger inputs?

public class PrintPrimes {
public static void main(String[] args) {
    Scanner s = new Scanner(System.in);  //it will take input
    int n = s.nextInt();
    int number = 3;
    System.out.print("2" + " ");
    while (n > 1) {
        if (checkPrime(number)) {
            System.out.print(number + " ");
            n--;
        }
        number++;
    }
  }

public static boolean checkPrime(int number) {
    for (int i = 2; i <= number / 2; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
  }
}

Your help is appreciated, Thanks!

user_9513184 · Answer

You can use the Sieve of Eratosthenes.

int n = s.nextInt();
boolean[] prime = new boolean[n + 1];
Arrays.fill(prime, true);
for(int i = 2; i * i <= n; i++){
    if(prime[i]){
        for(int j = i * i; j <= n; j += i){
            prime[j] = false;
        }
    }
}
for(int i = 2; i <= n; i++){
    if(prime[i]) System.out.print(i + " ");
}

Print first 100000 Prime numbers in Java

1 Answers