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

### 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?

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/
```
Associated Topics:
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