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?

  • 2
    $\begingroup$ 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? $\endgroup$ – N. S. Sep 21 '13 at 16:52
  • $\begingroup$ understood, actually $\endgroup$ – 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}$?

  • $\begingroup$ There is a typo, if $n=10$ then $\frac{n}{2}$ is not $10$ ;) $\endgroup$ – N. S. Sep 21 '13 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.