[SOLVED] Why do we check i <= sqrt(n) to find if a number is prime or not?

Why do we check i <= sqrt(n) to find if a number is prime or not?

I know this question has been answered before, but I didn't quite understand the explanation that was given on that question.

I was doing the 30 days of code on HackerRank, and one of the exercises was to check whether a number is prime or not. Unfortunately, I was not capable of doing it by myself, so I checked the given solution after many attempts. Even after looking at the solutions, I can't understand one of the lines:

// Check for primality using odd numbers from 3 to sqrt(n)
for(int i = 3; i <= sqrt(n); i += 2){
    // n is not prime if it is evenly divisible by some 'i' in this range
    if( n % i == 0 ){ 
        isPrime = false;
    }
}

Why is sqrt(n) used in the for loop?

Solution

Suppose n is a composite number.

Then, n = ab where a and b both are between 1 and n.

If a > sqrt(n) and b > sqrt(n), then this means that ab > sqrt(n)*sqrt(n) which basically implies that ab > n, this contradicts the assumption that ab = n.

Hence, either one factor (a or b) must be less than sqrt(n), or both be equal to it. So if n is composite, n must have a prime factor p <= sqrt(n)