Sieve of Eratosthenes Refinement

Question

From Wikipedia:

1. Create a list of consecutive integers from $2$ through $n$: $(2, 3, 4, ..., n)$.
2. Initially, let $p$ equal $2$, the smallest prime number.
3. Starting from $2p$, enumerate the multiples of $p$ by counting to $n$ in increments of $p$, and mark them in the list (these will be $2p$, $3p$, $4p$, ... ; the $p$ itself should not be marked).
4. Find the first number greater than $p$ in the list that is not marked. If there was no such number, stop. Otherwise, let $p$ now equal this new number (which is the next prime), and repeat from step $3$.

I understand all of the above except for the following refinement to the algorithm:

As a refinement, it is sufficient to mark the numbers in step 3 starting from $p^2$, as all the smaller multiples of $p$ will have already been marked at that point

Why is this the case? How can I be sure that they will have been marked? Could someone help me prove this?

Answer 1

A composite number $n$ must have a prime factor less than or equal to $\sqrt{n}$. This means that any composite less than $p^2$ has a prime factor less than $p$, and hence has already been crossed out by the time you are sieving with $p$.

Answer 2

Those are multiples $k\, p < p^2$ thus $k < p$ and the multiples of $k$, thus $k' \, k$, should have been marked already, including $k' = p$ if $p\, k \le n$. As now $k\, p \le n$ this should be the case.