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 firstname.lastname@example.org Copyright Springer-Verlag Berlin/Heidelberg 1996 ____ -Doctor Jodi, The Math Forum
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.