| Prime Home | Primer on Primes | In Search of Primes | Sieve of Eratosthenes | Files | References | Table of Contents |
Sieve of Eratosthenes |
| Introduction : Eratosthenes came up with such a simple effective method of finding primes, he still gets credit over 2000 years later. This is not some obscure demonstration, but a method that is still used in many prime number generators. |
| What is it ? The Sieve of Eratosthenes is a method of factoring all of the numbers in a given range. Since all of the primes are identified by not being factorable, the primes are also identified. As far as I am concerned the terms 'Sieve of Eratosthenes' and sieve are interchangeable it we are talking about prime numbers. I prefer sieve since it saves words and typing. |
How does it
work? Eratosthenes was aware that some
mathematical operations are easier than others.
Specifically it is easier to all a small integer to a
number under test than to divide by that same small
integer. He also noticed that if a number was factorable
by some prime factor, and you add that same prime factor
to the original number, the result was also factorable by
the same prime factor. We can eliminate all even numbers
as factorable. Table 1has all the odd numbers from 3 to
49. Since the squareroot of 49 is 7, we only have to test
for 3,5, and 7 as factors.
The columns marked f3, f5, and f7 are the columns that indicate factorable by the respective number. With the f3 column, we start at 3 since it clearly is factorable by 3. We then count down the column 3 places and mark that number as factorable by 3. We continue down the f3 column marking every third number as factorable by 3. For the f5 column we start with 5 and mark every 5th number as factorable by 5. For the f7 column we start with 7 and mark every 7th number as factorable by 7. When we are all done, the primes are easily identified. We have 3,5, and 7 since they are the test factors, and we have all the numbers that contain no factors of f3,f5 or f7. These include 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47. The sieve for numbers up to 255 is in Table 2. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Extending the
Sieve Part 1: Based on the examples above,
the sieve is useful but has some problems. For any range,
the lower limit needs to start at the lowest factor. For
us this is at 3. If we are screening for large prime
numbers, this is a serious problem. In this section we
are going to use an algorithmic approach, and not worry
to much about the theory. We start with an upper and lower limit to the target range. It is critical that both the upper and lower limit both be odd numbers. We then fill a data array with all of the odd numbers from the lower limit to the upper limit. We also have a list of factors we are going to test against the target array. Fill an array with the factors also. For each one of the factors we are going to have to find a starting point within the target data set. The process of finding the start numbers for each of the factors is as follows:
Repeat this process for all of the factors, eliminating invalid factors. When this is done, the sieve can be done using the start numbers with the respective factors. Clearly this is not as simple as the basic sieve, but the only major cost is 1 modulus operation for each factor. All the rest of the operations are addition and subtraction. |
|
|
