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

### Finding Primes: Sieve of Erastosthenes

```
Date: 4/1/96 at 17:32:15
From: Ms Susan M. Schmidt
Subject: Sieve of Erastosthenes

Dr Math:

Could you please elaborate on this subject a little more.  I have
to write a Pascal program to use this method and I can only find
little information about the Sieve of Erastosthenes.  Any info
would be greatly appreciated.
```

```
Date: 4/2/96 at 2:13:13
From: Doctor Jodi
Subject: Re: Sieve of Erastosthenes

Hi there!   At

http://www.utm.edu/research/primes/largest.html

you can find some information on the Sieve of Eratosthenes:

The document about finding primes is located at

http://www.utm.edu/research/primes/proving.html

1. Finding Very Small Primes

For finding all the small primes, say all those less than
10,000,000; the most efficient way is by using the Sieve of
Eratosthenes (ca 240 BC):

Make a list of all the integers less than or equal to n (greater
than one) and strike out the multiples of all primes less than or
equal to the square root of n, then the numbers that are left are
the primes.

For example, to find all the odd primes less than or equal to 100:
list the odd numbers from 3 to 100 (why even list the evens?) The
first number is 3 so it is the first odd prime--cross out all of
its multiples. Now the first number left is 5, the second odd
prime--cross out all of its multiples.  Repeat with 7 and then
since the first number left, 11, is larger than the square root of
100, all of the numbers left are primes. This method is so fast
that there is no reason to store a large list of primes on a
computer--an efficient implementation can find them faster than a
computer can read from a disk. Bressoud has a pseudocode
implementation of this algorithm [Bressoud89, p19] and Riesel a
PASCAL implementation [Riesel94, p6].

To find individual small primes trial division works okay. Just
divide by all the primes less than the square root. For example,
to show is 211 is prime, just divide by 2, 3, 5, 7, 11, and 13.
(Pseudocode [Bressoud89, pp21-22], PASCAL [Riesel94, pp7-8].)

Rather than divide by just the primes, it is sometimes more
practical to divide by 2, 3 and 5; then by all the numbers
congruent to 1, 7, 11, 13, 17, 19, 23, and 29 modulo 30--again
stopping when you reach the square root. This type of
factorization is sometimes called wheel factorization. Look in
most any elementary text on number theory for information about
these tests.

Suppose n has twenty digits, then it is getting impractical to
divide by the primes less than its square root, and it is
impossible if n has two hundred digits--so we need much faster
tests. We discuss several such tests below.
-----

That document also contains a lot more information about primes...
take a look at it some time!

Here's some other information that may be interesting to you:

I found a biography of Erastosthenes at

http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Eratosthenes.html

which, though not particularly pertinent to his sieve, may be
interesting to you.

__
Factorization and Primality Testing

1989 . XIII, 237 pp. 2 figs., Hardcover ISBN 3-540-97040-1
DM 102,-; oS 795,60; sFr 98,-

Book category: Advanced Textbook
Publication date : Available

(Undergraduate Texts in Mathematics. Eds.: J.H. Ewing; F.W.
Gehring; P.R. Halmos. )

Last update: March 6, 1996, URL:

http://www.springer.de/catalog/html-files/deutsch/math/3540970401.html

Copyright Springer-Verlag Berlin/Heidelberg 1996
____

-Doctor Jodi,  The Math Forum

```
Associated Topics:
High School Discrete Mathematics

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