printing Prime numbers in java

The first loop just for generating numbers from 2 to 100.

The second loop tries to find if the number is divisible by any other number. Here we try to divide a the number with a set of numbers (2 to prime_index).

Let’s say the number is 10, the prime index is 10/2 = 5 for first iteration(j = 2). Which means, if the number 10 is not divisible by any number between 2 and 5, it’s a prime number. It’s divisible by 2 itself making it a non prime number.

Let’s say the number is 9, now the prime index is 9/2 = 4 for first iteration(j = 2). Now, 9 % 2 gives 1 as reminder. So, loop continues for second iteration (j = 3). Now the prime index is 9/3 = 3 (Note here the prime index value is reduced from 4 to 3) So, now if the number is not divisible by 3, its decided as a prime number.

So, for every iteration, the prime index will reduce, making the number of iterations reduced.

Example for Number 97,
j = 2, prime index = 97/2 = 48 (no of iterations for loop)
j = 3, prime index = 97/3 = 32 (no of iterations for loop)
j = 4, prime index = 97/4 = 24 (no of iterations for loop)
j = 5, prime index = 97/5 = 19 (no of iterations for loop)
j = 6, prime index = 97/6 = 16 (no of iterations for loop)
j = 7, prime index = 97/7 = 13 (no of iterations for loop)
j = 8, prime index = 97/8 = 12 (no of iterations for loop)
j = 9, prime index = 97/9 = 10 (no of iterations for loop)
j = 10, prime index = 97/10 = 9 (loop exits as condition failed 10 <= 9 and declares 97 as a prime number)

Now, here the loop actually took 10 iterations instead of the proposed 48 iterations.

Let’s modify the code for better understanding.

public static void main(String args[]) {    
        // Number from 2 to 100
    for(int i=2; i < 100; i++) { 
       if (isPrimeNumber(i)) {
            System.out.println(i + " is prime");
       }
    }
}

Now, lets see a method isPrimeNumberNotOptimized() which is not optimized.

private static boolean isPrimeNumberNotOptimized(int i) {
    for(int j=2; j <= i/2; j++) {
        // if it is, then its not prime 
        if((i%j) == 0) {
            return false;
        }
    }
    return true; 
}

And, another method isPrimeNumberOptimized() which is optimized with prime index.

private static boolean isPrimeNumberOptimized(int i) {
    for(int j=2; j <= i/j; j++) {
        // if it is, then its not prime 
        if((i%j) == 0) {
            return false;
        }
    }
    return true; 
}

Now, both methods will run and print the prime numbers correctly.

But, the optimized method will decide 97 is a prime number at 10th iteration.

And, the non-optimized method will decide the same in 48th iteration.

Hope, you understand it now.

FYI: prime index is the number we used for calculation. Such that if a number is not divisible between 2 & the derived prime index, its a prime number