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. 

Perhaps this book would help 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    
Your comments are welcome at promotion@springer.de 

Copyright Springer-Verlag Berlin/Heidelberg 1996 
____

-Doctor Jodi,  The Math Forum