Code optimization (Prime no.)

Question:

To take 'n' inputs from user and tell if the number is prime or not.

Let's solve this step by step and analyze how we can reduce it's time complexity.
We know that prime numbers are the numbers which are divisible by only 1 and the number itself.
So the main concept that would be used here is that, we need to check the remainder when we divide the number by each number, if the remainder is 0, the number is completely divisible by that number and then we will increase the value of count, which would be a counter variable initialzed to count the number of times the input num got completely divided. On the basis of which we will tell if the num is prime or not.

So the first code that i wrote for this was:

Output of which appears as:

This code is technically correct but the number of time it iterates makes its time complexity very high.

So the first and most basic change I did was to decrease the number of iterations in the for loop of div.

I changed it from:
for(int div = 1; div <= n; div++ ){
if(n % div == 0){
count++;
}
if(count == 2){
System.out.println("Prime");
}
}

to:
for(int div = 2; div < n; div++ ){
if(n % div == 0){
count++;
}
}
if(count == 0){
System.out.println("Prime");
}

which reduces two iterations, we know that the prime nums are divisible by 1 and the num itself so we can exclude these two cases and check if any other num completely divides the num, if it does then the num is not prime and if it doesn't the num is prime.
So this reduces two iterations yet it does not help us significantly.

There's a pattern we need to analyze in the divisors of a number, take an example:
24, it's divisors can be written as:
1 x 24
2 x 12
3 x 8

4 x 6

6 x 4
8 x 3
12 x 2
24 x 1

We know that square root of 24 is 4.89, so did you notice some pattern in the divisors of the number around it's sqrt, it is clear that the number of times a num can be completely divided before it's sqrt is same as the no. of diviors it would have after the sqrt.

So instead of iterating the second loop till n we can iterate it till sqrt of n which would reduce the iterations to almost half.

So the code would now look as follows:

for(int div = 2; div * div < n; div++ ){
if(n % div == 0){
count++;
}
}
if(count == 0){
System.out.println("Prime");
}
we cannot write sqrt n directly so instead I wrote it as div * div < n

But there's one more optimization that we could do in this, i.e. if a number is divisible by any other number instead of 1 and the num itself then it is called prime, even if there's only one num other then these two, so what we can do is break the loop as soon as we find the very first number that is divisor of the num except 1 and itself.

So the final code would look as follows: