Writing an isPrime function in java and using Math.sqrt

Question

When writing an isPrime function to return a Boolean in Java, I have seen a lot of examples where people use Math.sqrt(number) in their for loop. Can someone explain why and what this function is doing in the for loop? I have attached an example for reference. Thanks!

    public boolean isPrime(int n) {
       if (n <= 1) {
           return false;
       }
       for (int i = 2; i < Math.sqrt(n); i++) {
           if (n % i == 0) {
               return false;
           }
       }
       return true;
    }

Answer 1

How do you know if a number n is a prime? The first strategy would be to test all numbers, from 2 to (n-1). For every value i, check if n divides by i. If you find such a i, then n is not a prime.

But do you really need to test all values? No, as soon as you have reached the square root of n, you would be testing the same "pair" of values. In other words, sqrt is there to limit the number of tests to be done, hence to improve the performance.

Answer 2

If a number is not a prime, it can be factored into two factors f1 and f2

If f1 and f2 are > the sqrt of the number, f1*f2 would be > the number. So at least one of those factors must be <= to the sqrt of the number. To see if a number is actually prime, we only need to test factors that are <= to the sqrt.