Wikipedia, explains the basic algorithm of eratosthenes and several pages such as this, explain the refinements made on the sieve. But the thing I'm having a hard time to find is:
Why does the next number after the smallest prime being crossed out with its multiple have to be a prime? Is there a proof for this?
For example:

in the set s = {2,3,4,5,6,7,8,9}, after crossing out all the multiples of 2 (including 2 itself), why does 3 have, to be a prime?

  • 1
    $\begingroup$ keep on working, I'm sure you can find it yourself $\endgroup$
    – reuns
    Jul 8, 2016 at 10:15

3 Answers 3


By induction:

Assume you have found all primes smaller than $n$. All the multiples of these primes have been struck out.

If $n$ is composite, it has a nontrivial prime factor smaller than itself and it is struck out. So it $n$ remains, it must be a prime.

Then you have found all primes smaller than $n+1$.


By contradiction: If it is not a prime, it is divisible by some smaller factor. So it should be already crossed.


I find an easy way to think of the why, is

all the numbers that are being crossed off are multiples of the smaller numbers

if it hasn't been crossed off then it isn't a multiple of any smaller number

therefore it is a prime.


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.