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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/