Prime Numbers and the Sieve of EratosthenesDate: 10/20/2003 at 14:12:55 From: Andrew Subject: Prime Numers How can I figure out the last or largest prime number I need to use in the "Sieve of Eratosthenes" in order to find all the primes between 1- 500? Date: 10/20/2003 at 14:45:56 From: Doctor Edwin Subject: Re: Prime Numers Hi, Andrew. I'm going to answer a question that is closely related to what you are asking, and then show you how it applies to your question. Keep in mind that the Sieve of Eratosthenes is based on finding and canceling numbers which have factors and leaving behind only the primes. Here's the related question: If I want to check a number (let's call it N) for factors, and I'm going to start with 2 and work my way upward, how high do I have to go before I can say that N is prime? You know that factors come in pairs. You also know that if one factor is small, its partner must be large. So with 500, we know that 2 is a factor, and its partner is 250. 20 is also a factor, and it's bigger than 2, so its partner, 25, is smaller than 250. So as the smaller partner gets bigger, the bigger partner gets smaller. Does that make sense? If not, write back and I'll try to explain that a little more. The point is that I don't have to look for the larger partner. If I'm starting by checking whether N is divisible by 2, and then by 3, and then by 5, and 7, and 11, etc., then I'll hit the smaller partner before I hit the larger partner. Let's say I'm checking whether 500 is prime. I don't have to check as high as 250. If 2 isn't a factor, then 2's partner isn't a factor either. Similarly, I don't have to check as high as 50. If 50 were a factor, then 10 would have been a factor. So, how high do I have to count? High enough to be sure I would check the smaller partner of any factor pair. Now as I said, as the smaller partner gets bigger, the bigger partner gets smaller. They get closer and closer together and they meet somewhere in the middle. That's the point you have to check to. So where do they meet? They meet where the smaller partner and the larger partner are equal. At what point are the two partners the same? Let's try with an example. Let's take 36. The pairs of factors are 2 * 18, 3 * 12, 4 * 9, and 6 * 6. You see how they get closer together and then meet? How about 64? 2 * 32 4 * 16 8 * 8 So when I'm checking for the factors of 64, I don't have to check any higher than 8. For every factor greater than 8, there's another one smaller than 8. I'll leave the last step up to you. How is 8 related to 64 and 6 related to 36? Given that, if I want to check a number N to see if it's prime, what's the largest factor I have to try? Now back to your question. What's the highest prime number that you need to run through the sieve to be sure that you've eliminated all non-primes between 1 and 500? Can you see that the same logic applies here as worked in finding factor pairs? Since the factors 'meet' at SQRT(500) or approxinately 22.3, you won't have to run any number larger than that through the sieve. Write back if this isn't clear. - Doctor Edwin, 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/