- Circle the next number bigger than that is not yet crossed out, call it .
- Cross out every th number after , that is, all the multiples of . These are not prime since they are multiples of .
This is an efficient way to find all the primes up to a given limit. Note that it doesn’t require doing any division or factoring, just adding. Here’s the image of the sieve again:
Some questions for you to ponder:
- Why can we always cross out multiples of each prime using parallel straight lines?
- When will the lines be vertical? When will they be diagonal?
- Is there only one way to cross out multiples of each with straight lines, or could we have chosen different lines?
- Why are the primes on the top row circled, while the rest of the primes are in boxes? What’s the difference?
And just for fun here’s the sieve diagram for , one of my favorites. Click here for a larger version.