Prime Check

Given an integer $N$, determine if it is a prime number. A prime is a number greater than 1 that has no divisors other than 1 and itself. Input: 29 → True. Input: 30 → False.

If $N$ has a factor $f > \sqrt{N}$, then $N/f < \sqrt{N}$ is also a factor — so the smaller factor would already have been found. This means we only need to test divisors up to $\sqrt{N}$, reducing the check from $O(N)$ to $O(\sqrt{N})$.

1. Return False for $N \leq 1$ (by definition, not prime).
2. Return True for $N = 2$ (only even prime).
3. Return False for even $N > 2$.
4. Loop odd divisors from 3 to $\lfloor \sqrt{N} \rfloor + 1$ (step 2).
5. If any divisor evenly divides $N$, return False.
6. Otherwise return True.

• Checking all $N$ divisors instead of just up to $\sqrt{N}$
• Forgetting that 2 is prime and even (the only even prime)
• Using range(2, N) instead of range(3, int(N**0.5)+1, 2)

The $\sqrt{N}$ optimization is one of the most important tricks in number theory problems. This exact technique is used in the Sieve of Eratosthenes (Day 6) and prime factorization (Day 7).