# 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++) {
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