# 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:

```python
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(n**0.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! 💻