Here is an exercise:
Show that when finding the primes from 2 to $n$ using the Sieve of Erathosthenes, we can stop crossing out once $p \geq \frac{n}{2}$.
Let $p$ be denoted by a star.
Suppose $n = 10$. Then $$[2*, 3*, \not 4, 5, \not 6, 7, \not 8, \not 9, \not 10]$$
First of all, I am able to stop crossing out when $3 \geq \frac{10}{2}$, a contradiction. This also holds for $n = 11, n = 12,$ etc...How would I then be able to solve this problem?
On
If n = 10, the statement of the problem is that you can stop at $p = \frac{n}{2} = 5$. But this is an upper bound. Its not a contradiction if you can stop at an earlier number. And 3 most definitely is not $\geq \frac{10}{2}$
As for the actual problem, what is the first number that you would cross off when $p = \frac{n}{2}$?
In fact, you can stop crossing out as soon as $p\geq \sqrt{n}$, since if $n$ has a factor $q$ greater than $\sqrt{n}$, then $\frac{n}{q}\leq\sqrt{n}$.
Also, $3<5=\frac{10}{2}$.