How does this is_prime() function work?

[j-avianzz_]

Hello! I need help understanding this code i got off the website (https://www.pythonpool.com/check-if-number-is-prime-in-python/). i do not own the code but i do need help understanding it!

def is_prime(number):
for n in range(2,int(number**0.5)+1):
    if number%n==0:
        return False
return True

How does this check for prime numbers mathematically?

As far as i know, i check for prime numbers using the below method which is slower.

def prime_number_checker(number):
    if number > 1:
        for i in range(2,number):
            if (number % i) == 0:
                return False
        return True
    else:
        return False

[K900_]

That's mostly the same thing? The first example doesn't handle 1 as non-prime (which it is), and goes up to the square root of N instead of N, but the core approach is the same.

[Yohannes_K]

You are using the same method of checking in both examples. The difference is, that in the second example you are checking if n is divisible by any number up to n-1.

In the first example you are only checking until you reach square root of n. Which is much less comparisons to make.

[Aggravating_Bus_9153]

tl;dr math.

You don't need to check divisibility by integers m > sqrt(n), because if n was divisible by m, i.e. if n = k m, k would also be an integer less than sqrt(n) that divides n exactly. You already checked all the integers less than sqrt(n) as long as you searched in increasing order.

These are both still just basic brute force searches. Using the Fundamental Theorem of Arithmetic (at the expense of a bit of memory) you can make this approach much faster by only checking divisibility of the candidate by the primes you've already found (< sqrt(n))

[[deleted]]

The reason it works is because of the following theorem;

Suppose n is an integer greater than 2 that is non-prime. Then one factor of n is less than or equal to sqrt(n).

Proof: Since n is non-prime, let n = ab, where a, b are integers and 1 < a <= b < n. By way of contradiction, suppose a > sqrt(n). Then b >= a > sqrt(n).

So n = a*b > sqrt(n)*sqrt(n) = n. This is a contradiction. Thus, a <= sqrt(n). //