Let us suppose we are given an integer $N$ in binary representation. Let us consider the following algorithm to check if $N$ is a prime.
- For every $i$ such that $2 \leq i \leq\lceil\sqrt{N}\rceil$, check if $i$ divides $N$.
- If any of the $i$ 's divides $N$, return that $N$ is not a prime.
- Else, return that $i$ is a prime.
Based on this information, answer the following.
- Explain why iterating till $\lceil\sqrt{N}\rceil$ is sufficient.
