What's the logic behind if n < i*i: return True?

def isPrime(n, i = 2):
 
    # Base cases
    if (n <= 2):
        return True if(n == 2) else False
    if (n % i == 0):
        return False
    if (n < i*i):
        return True
 
    # Check for the next divisor
    return isPrime(n, i   1)

CodePudding user response：

For each factor f, there is a complement n/f. If the factor is less than sqrt(n), the complement is bigger, and vice versa. So, if we checked all factors up to and including sqrt(n), and found none, it is sufficient to say that there are no other factors.

CodePudding user response：

At each iteration, we establish that n is not divisible by an integer less than or equal to i. If n were not a prime, then by definition n = x * y where x and y are positive integers. Both x and y must be greater than i as mentioned earlier. It follows that n = x * y must be greater than i * i for it to possibly be a prime.