The Sieve, and Ceiling, of EratosthenesDate: 07/27/2012 at 10:40:03 From: Lin Subject: Eratosthenes Sieve - when to use 11 I want to teach my kids about prime numbers with the Eratosthenes Sieve, but I have noticed that some websites say to use the factors, 2, 3, 5, and 6, while others say to use all those numbers AND the number 11. Why is that so? and won't it make a difference to the answer? Thank you. Date: 07/27/2012 at 11:05:56 From: Doctor Peterson Subject: Re: Eratosthenes Sieve - when to use 11 Hi, Lin. Can you give me an example of such a site? How they word it will make a difference. Also, in the sieve of Eratosthenes, you only mark off multiples of prime numbers, so 6 would not be used; perhaps you meant 7? How far you go down the list of primes depends on how big a sieve you are making. Most likely those that used 11 were finding primes past 100; or else, possibly, they were using 11 to help students discover the point I'm about to make, the upshot of which is that, if you are finding primes through 100, you DON'T need to go as far as 11. That's a good thing to experience. Let's do a smaller sieve, up to 50, and see how far we have to go. 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 We first mark 2 as a prime and strike out all its multiples: ( 2) 3 / 5 / 7 / 9 // 11 // 13 // 15 // 17 // 19 // 21 // 23 // 25 // 27 // 29 // 31 // 33 // 35 // 37 // 39 // 41 // 43 // 45 // 47 // 49 // Now, the first remaining number, 3, has been shown to be a prime, because it is not a multiple of any prime before it. So we repeat the process with 3, striking out 9, 15, 21, 27, 33, 39, and 45: ( 2)( 3) / 5 / 7 / / // 11 // 13 // // // 17 // 19 // // // 23 // 25 // // // 29 // 31 // // // 35 // 37 // // // 41 // 43 // // // 47 // 49 // Now we see that 5 is the next prime, so we strike out all its multiples that remain -- namely, 25 and 35: ( 2)( 3) / ( 5) / 7 / / // 11 // 13 // // // 17 // 19 // // // 23 // // // // // 29 // 31 // // // // // 37 // // // 41 // 43 // // // 47 // 49 // Now the next prime is 7. But when we go to strike out its multiples, we find that there is only one -- namely, 49: ( 2)( 3) / ( 5) / ( 7) / / // 11 // 13 // // // 17 // 19 // // // 23 // // // // // 29 // 31 // // // // // 37 // // // 41 // 43 // // // 47 // // // We COULD now try the next prime, 11; but we'd have nothing to do! Why is this? Well, did you notice that in each step, the first number we struck out was the SQUARE of the prime we were working with? 2^2 = 4 3^2 = 9 5^2 = 25 7^2 = 49 There's a good reason for that: any multiple of, say, 7 less than 7*7 has already been struck out because the other factor is smaller than 7! So when we come to 11, the first number we'd strike out would be 121, and that's not in our table of the first 50. (It isn't even in the table for primes through 100.) Therefore, we already know that nothing more will be stricken (ever!), so we can mark all the remaining numbers as prime: ( 2)( 3) / ( 5) / ( 7) / / // (11) // (13) // // // (17) // (19) // // // (23) // // // // // (29) // (31) // // // // // (37) // // // (41) // (43) // // // (47) // // // The lesson here is that the first number you DON'T have to use is the first prime the square of which is GREATER than your maximum number, or that squares beyond the largest number in the sieve. To put that the other way around, you only have to use primes that are LESS than the SQUARE ROOT of the maximum. So one way to present the sieve of Eratosthenes up to 100 is to just tell your kids that they can stop after 7 -- but then they may not know why, and the process may seem arbitrary. For the sake of insight, deliberately include 11 before exploring why you don't need to use it. Now, suppose you were making a sieve for numbers through 1000. What is the last prime you would have to use? It won't be either 7 or 11. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/