The Sieve of Oregon
Home My Pictures My Car My Dream Car My "Perls" Prime Numbers	In the late 70’s an article in Scientific American describing Public Key Cryptography captured my imagination. For my senior project in college, I wrote a program on my HP41C programmable calculator that would do Public Key encryption and decryption based on small 5 digit prime numbers. (Thanks to C. Claiborn who proofed and typed that paper for me in the days before word processors!) This sparked an interest in generating and testing prime numbers. The Sieve of Eratosthenes is the original prime number generator. Following is a small improvement on the Sieve that I invented while living in Oregon. My improvement is summed up in two sentences: 1) A finite set of prime numbers defines a repeating pattern of numbers that are multiples of one or more of those primes, (and therefore not prime) and the length of that repeating pattern is the product of those primes. 2) Instead of using storage for each number and marking it as composite or prime, you can keep a list of the differences between consecutive prime numbers. So here’s how my sieve works: 1-Start with 1. 2-(Disqualify it because it is too special.) 3-Start a distance list with the number 1. 4-The next prime, P, is 1 plus the first number in the distance list {1}. (P=1+1=2). 5-Make a new distance list by concatenating the old one P times {1,1}. 6-Shorten the distance list as follows: 6a-Start with 1, and then add each member of the distance list to it, while testing if the current sum is divisible by the current P. 6b-If so, replace this member of the distance list and the next one with their sum. (The distance list becomes {2}). 7-Loop back to step 4. Here are those steps continuing with specific values: 4-The next prime, P, is 1 plus the first number in the distance list {2}. (P=1+2=3). 5-Make a new distance list by concatenating the old one P times {2,2,2}. 6a-The successive sums are 3,5,7. 6b-Since 3 is a multiple of 3, the first two items of the list are combined, and the list becomes {4,2}. 4-The next prime, P, is 1 plus the first number in the distance list (4). (P=1+4=5). 5-Make a new distance list by concatenating the old one P times {4,2,4,2,4,2,4,2,4,2}. 6a-The successive sums are 5,7,11,13,17,19,23,25,29,31. 6b-Since 5, and 25 are a multiples of 5, the list becomes {6,4,2,4,2,4,6,2}. Etc! Here is a perl script that does this algorythm.
Back Home