Determine if a number is prime

Let us explore how to determine if a number is prime. Prime numbers have fascinating mathematical properties. A number is considered prime if it is only divisible (without a remainder) by one and itself.

• 👍🏼 The number 7 is prime. It is only divisible by 1 and 7.
• 👎🏼 The number 8 is not prime. It is divisible by 1, 2, 4, and 8.

We can determine if a number is prime by checking if it is divisible by any other numbers, excluding 1 and itself. If we find such a divisor, the number is not prime.

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

Although the above function is correct, there is an optimization. It is unnecessary to test all numbers up to n. It suffices to test up to sqrt(n) + 1. For example, you do not need to test if 10, 11, or 12 divide 13 because they are greater than 4. With this knowledge, we can optimize the code.

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

Now we can use our function to verify that 41 is prime.

p = 41
print(f"{p} is prime? {is_prime(p)}")

✏️ Exercises:

• Write a function that searches for a large prime number, with 8 digits.