Finding Prime Number in Java

Question

I came across a Java program which finds whether the given number is a prime. here is the code.

class FindPrime {
    public static void main(String args[]) {
        int num;
        boolean isPrime;
        num = 14;

        if (num < 2) 
          isPrime = false;
        else 
          isPrime = true;

        for (int i = 2; i <= num / i; i++) {
            if ((num % i) == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) 
          System.out.println("Prime");
        else 
          System.out.println("Not Prime");
    }
}

Here, I'm not sure why the condition i <= num/i is used in the for loop. Can someone please explain me?

Answer 1

The limiting condition i <= num / i is a performance optimisation:

Given e.g. num = 11 and i = 3, we have so far checked if 11 can be divided by 2 (no) and now are moving to 3 and we should check it, the answer is no it cannot be divided by 3. Now we are moving to 4, should we still check if 11 can be divided by it? Such a division will yield 2.75, a value smaller than 3 that we have already checked. Any higher i will yield even smaller values all of which we have already checked, so there is no sense checking further. We know the answer by now.