finding prime number using the square root method

Question

I was able to write a function for the prime number using this way

def isprime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True

%timeit [i for i in range(1000) if isprime(i)]
7.94 ms ± 273 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Then I found that there's an even faster way to write this using the square root but I couldn't understand the working of this. Can anyone explain this code in easier terms and why it works?

def isprime(num):
    if num > 1:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True

%timeit [i for i in range(1000) if isprime(i)]    
1.94 ms ± 54.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

If this is a duplicate please let me know I will delete it instantly.

Answer 1

This is best explained by example. Suppose that you wish to know whether 143 is prime. Do you really need to try to divide by 142, 141, 140, 139, and so on? Obviously, none of those divides 143; they're too big.

But see:

• 143 % 2 == 1
• 143 % 3 == 2
• 143 % 5 == 3
• 143 % 7 == 3
• 143 % 11 == 0

Apparently, 11 divides 143. Not prime.

Now let's try 145. Is 145 prime?

• 145 % 2 == 1
• 145 % 3 == 1
• 145 % 5 == 0

Apparently, 5 divides 145. Not prime. Now consider, we could have tried

• 145 % 29 == 0

That would have worked because 145 == 5*29, but it wasn't necessary to try a factor as large as 29. The 5 sufficed.

So think about this. If a composite number n == a*b has two factors, a and b, suppose that b > sqrt(n). In that case, it must be the case that a < sqrt(n), for, were it not so, then a*b could not equal n. Indeed, were it not so, then a*b would be larger than n, implying that a*b were not a proper factorization of n.

All you need to do is to find the value of the smaller factor. The smaller factor is less than, or is at most equal to, the square root. If no factor less than or equal to the square root is found, it follows that the number under investigation is prime.

Answer 2

You only need to check factors up to a number's square root to determine whether the number is prime -- any factor greater than its square root would have to be paired with one less than its square root, and you've already checked them.

This allows the second implementation to finish its loop much earlier (e.g. you only need to test 2..31 to determine that 997 is prime, rather than 2..996 as in the first implementation).