Sieve of Eratosthenes - why can we begin marking off from the square of a number?

Question

In the Sieve of Eratosthenes algorithm, whenever we identify a number $i$ as prime, we can mark off all numbers from $i^2$ to our limit $n$ as not prime, as opposed to starting from $2i$. How do we know that this optimization is safe?

Answer 1

Because every number less than $i^2$ is either a prime or has a divisor less than $i$.

Reason: if it has two divisors at least $i$, then its value is at least $i^2$.

Answer 2

You can see this by induction on the primes. For the base case, $p = 2$, you clearly mark off all multiples of $2$ between $2$ and $n$ since $2^2 = 4$.

For the inductive hypothesis, assume $p$ is the next prime, and that multiples of primes $q$ for $q < p$ have already been marked off.

We mark off all multiples of $p$ between $p^2$ and $n$, so the only way you could have a problem, is if there is some non-prime $k < p^2$. In this case, you want to make sure that $k$ is still marked as non-prime.

But if $k$ is non-prime, use the fundamental theorem of arithmetic to write it as a product of its prime factors: $k = q_1^{m_1} ... q_r^{m_r}$ where $1 \le m_i$ and $ q_i$ is prime for all $i$. Since $k < p^2$, at least one of its prime factors $q_i$ must be less than $p$.

(Otherwise, you have $q_i \ge p$ and therefore $k = q_1^{m_1} ... q_r^{m_r} \ge p^{m_1 + ... + m_r}$. But since $k$ is composite, $m_1 + ... + m_r \ge 2$, which would mean $k \ge p^2$, a contradiction.)

But then $k$ is a multiple of a prime factor $q_i < p $, so by the inductive hypothesis $k$ has already been marked off as non-prime, so the algorithm works.