Mathematics : if one divisor of a dividend is greater than the square root of the dividend, then the quotient is smaller than the square root of the dividend.
We have ij = n, i > 0, j > 0 if i > sqrt(n) ij > sqrt(n) j n > sqrt(n) j sqrt(n) > j Hence we have to check the primality of a number by trying to divide it only upto the square root of the number. Thank you, Praveen Kumar Sirohiwal.