CODEWITHSUNDEEP
pythonalgorithmmathlogicprimes
Cesar Arturo Solano
Cesar Arturo Solano

Reputation: 1

Recursive Function - Is Prime

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)

Upvotes: 0

Views: 128

Answers (2)

Dafang Cao
Dafang Cao

Reputation: 907

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.

Upvotes: 0

Marat
Marat

Reputation: 15738

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.

Upvotes: 1

Related Questions