# Sieve of Erathosthenes - when can I stop crossing out?

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?

• That's not a contradiction, it just tells you that $\frac{n}{2}$ is not the BEST place to stop. The point is that if you go until $\frac{10}{2}$, you get all primes, don't you? – N. S. Sep 21 '13 at 16:52
• understood, actually – Don Larynx Sep 21 '13 at 16:54

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}$.
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}$?
• There is a typo, if $n=10$ then $\frac{n}{2}$ is not $10$ ;) – N. S. Sep 21 '13 at 16:56