Problem 14: Check if a Number is Prime

Hey everyone! 👋

Today, we're solving a classic mathematical problem: Checking if a Number is Prime.

The Problem

The goal is to write a function that determines whether a given number is prime.

• A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
• The function should return True if the number is prime, and False otherwise.

Examples:

• is_prime(7) → Should return True (7 is only divisible by 1 and 7)
• is_prime(10) → Should return False (10 is divisible by 1, 2, 5, and 10)
• is_prime(2) → Should return True (2 is the only even prime number)

The Solution

Here is the Python implementation:

def is_prime(n):
    """
    Checks if a number is prime.
    """
    # Numbers ≤ 1 are not prime by definition
    if n <= 1:
        return False

    # 2 is the only even prime number
    if n == 2:
        return True

    # Check if n is even (and not 2)
    if n % 2 == 0:
        return False

    # Check odd divisors from 3 up to the square root of n
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False

    return True

# Test cases
print(is_prime(7))   # True
print(is_prime(10))  # False
print(is_prime(2))   # True

Code Breakdown

Let's walk through the code line by line:

1. def is_prime(n):

   • Defines a function named is_prime that takes an integer n as input.

2. if n <= 1:

   • Checks if the number is less than or equal to 1.
   • By mathematical definition, numbers ≤ 1 are not considered prime, so we return False.

3. if n == 2:

   • Special case: 2 is the only even prime number.
   • If n is 2, we immediately return True.

4. if n % 2 == 0:

   • Checks if n is even (divisible by 2).
   • Since we've already handled the case where n == 2, any other even number is not prime.
   • Returns False for all even numbers greater than 2.

5. `for i in range(3, int(n0.5) + 1, 2):`**

   • This is the optimization key! We only need to check divisors up to the square root of n.
   • Why? If n has a divisor greater than √n, it must also have a corresponding divisor smaller than √n.
   • n**0.5 calculates the square root of n.
   • int(...) converts it to an integer.
   • + 1 ensures we include the square root itself in the range (since range is exclusive of the end value).
   • 2 as the step means we only check odd numbers (3, 5, 7, 9, ...), skipping all even numbers since we already know they're not prime.

6. if n % i == 0:

   • Checks if n is divisible by the current value of i.
   • If it is, n has a divisor other than 1 and itself, so it's not prime.
   • Returns False immediately.

7. return True

   • If we've checked all possible divisors and found none, the number is prime.
   • Returns True.

Example Walkthrough

Let's trace the function with is_prime(29):

1. Check: 29 <= 1? No, continue.
2. Check: 29 == 2? No, continue.
3. Check: 29 % 2 == 0? No (29 is odd), continue.
4. Loop: Check divisors from 3 to √29 ≈ 5.38, so we check 3 and 5.
   • i = 3: 29 % 3 == 0? No (29 ÷ 3 = 9 remainder 2)
   • i = 5: 29 % 5 == 0? No (29 ÷ 5 = 5 remainder 4)
5. Result: No divisors found, return True. ✅

Now let's trace is_prime(15):

1. Check: 15 <= 1? No, continue.
2. Check: 15 == 2? No, continue.
3. Check: 15 % 2 == 0? No (15 is odd), continue.
4. Loop: Check divisors from 3 to √15 ≈ 3.87, so we check 3.
   • i = 3: 15 % 3 == 0? Yes! (15 ÷ 3 = 5)
5. Result: Divisor found, return False. ❌

Key Optimizations

This implementation uses several clever optimizations:

• Early Returns: We return False as soon as we find any divisor, avoiding unnecessary checks.
• Reduced Search Space: Only checking up to √n dramatically reduces the number of iterations.
• Skip Even Numbers: After handling 2, we skip all other even numbers by stepping by 2 in our loop.

These optimizations make the function efficient even for larger numbers! 🚀

Happy coding! 💻