Associated Topics || Dr. Math Home || Search Dr. Math

### How does the Sieve of Eratosthenes Work?

Date: 10/29/2002 at 17:28:20
From: S
Subject: Why does it work? and how?

I'm in the 6th grade and right now we are working on the "sieve of
Eratosthenes." I'm wondering why and how it works.

Thanks for all your help - you make math actually kinda fun!
-S

Date: 10/29/2002 at 18:55:15
From: Doctor Ian
Subject: Re: Why does it work? and how?

Hi S,

We start out with some set of numbers. Normally, that's 1 to 100, but
I don't want to write all those, so I'm going to go from 1 to 30. The
idea stays the same, though.

1  2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

We start by getting rid of 1, because the definition of 'prime'
excludes 1:

2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

The smallest prime is 2.  But anything that is _divisible_ by 2 can't
be prime, right?  So we can keep 2, and cross out all its multiples:

2  3     5     7     9
11    13    15    17    19
21    23    25    27    29

As you can see, that wipes out half the numbers we started with!

The next prime is 3.  We're going to keep that, and again, we'll wipe
out the multiples of 3 - since if something is divisible by 3, it
can't be prime:

2  3     5     7
11    13          17    19
23    25          29

Now, what about 4? When we eliminated multiples of 2, we also
eliminated multiples of 4, 6, 8, and every other even number! This is
how the sieve works so quickly: every time you eliminate the
multiples of a prime number, you never have to check those multiples.

So we can just skip to the next prime number, which is 5. Removing
the multiples of 5 leaves us with

2  3     5     7
11    13          17    19
23                29

And at this point, we'd need numbers over 30 in the sieve to see any
effects, since everything we have left is prime.

But do you see the main idea? It's sort of like a game that you can
play with an audience full of people. Ask everyone to stand up. Then
tell everyone with an 'a' in his or her last name to sit down. Then
tell everyone with an 'e' in a last name to sit down. (Note that
someone named 'Apple' would already be sitting.) Then do the same for
'i', 'o', and 'u'. Who will be left standing? Only people with no
vowels in their names! That is, people with names like Ng, or Kyzyl,
or Flynn, or Zbrtzk.

If we order the vowels from most frequent to least frequent (eaoiu),
then each vowel will eliminate fewer people - partly because it's used
less often, and partly because many people have more than one vowel in
their names (in much the same way that 6 gets eliminated as a multiple
of 2, so it isn't around to be eliminated as a multiple of 3).

Does this make sense?

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/
Associated Topics:
Elementary Prime Numbers
Middle School Prime Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search