Prime Check

Write a function that returns True if a number n is prime, and False otherwise. A prime number is greater than 1 and has no positive divisors other than 1 and itself. Input: 7 → True. Input: 12 → False (divisible by 2, 3, 4, 6). Input: 1 → False.

The naive approach checks all numbers from 2 to n-1, which is O(N). The key optimization is: if n has a divisor d, then n/d is also a divisor. One of them must be ≤ √n. Therefore, we only need to check from 2 to √n. This reduces the complexity from O(N) to O(√N), a massive improvement for large numbers.

1. If n ≤ 1, return False (1 is not prime by definition). 2. Loop from 2 to int(√n) + 1. 3. If any number in this range divides n evenly (n % i == 0), return False. 4. If no divisor is found, return True.

- Forgetting that 1 is NOT a prime number - Using range(2, n) instead of range(2, int(n**0.5) + 1), making it O(N) instead of O(√N) - Not handling 2 correctly: it is the only even prime number - Using n**0.5 without int(), which can cause floating-point comparison issues

The √N optimization is a fundamental technique in number theory. It reduces a 1-billion-step loop to about 31,623 steps. This same principle (if a factor exists, its complement must be on the other side of √N) appears in many problems. For even faster primality testing at scale, look into the Miller-Rabin test.