Prime Numbers and the Sieve of Eratosthenes

Date: 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/