2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 ...The first value in the table is two. None of the values in the table are crossed out so two is also the first non-crossed out value in the table. Identify it as prime with an over line, then cross out every second number (every multiple of two).
_ 2, 3, X, 5, X, 7, X, 9, X, 11, X, 13 ...The next non-overlined and non-crossed out number is three. Identify it as prime with an overline, then cross out ever third number (every multiple of three).
_ _ 2, 3, X, 5, XX, 7, X, X, X, 11, XX, 13 ...The numbers six and twelve have been crossed out twice since they are multiples of both two and three. Continue the procedure. Five is the next non-overlined and non-crossed out number. Overline five and cross out every fifth number.
_ _ _ 2, 3, X, 5, XX, 7, X, X, XX, 11, XX, 13 ...The next prime number is then seven. Since twice seven is greater than the largest visible number in our list, all the remaining visible numbers are prime. Given a set of sequential integers starting with two, we can find all the prime numbers in the set. Observe that in the list above several numbers were crossed out more than once. This occurs because they have more than one prime factor. If a number in our list had three prime factors it would be crossed out three times. The smallest such number is 30. The sieve of Erastothenes identifies which numbers are not prime. The primes are all the numbers left over. The next prime number sieve identifies each non prime exactly once. It identifies composite numbers in a different order from the sieve of Erastothenes.
_ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, ...Multiply every crossed out or overlined number by two and cross those numbers out. 2 times itself is 4. Cross out 4. Since 4 is crossed out multiply it by 2 to get 8. Cross out 8. Continue and cross out 16 and 32. All of these are powers of 2.
_ 2, 3, X, 5, 6, 7, X, 9, 10, 11, 12, 13, 14, 15, X, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, X, ...Now the next non-overlined and non-crossed out number is three. Overline three to indicate it is the next prime number.
_ _ 2, 3, X, 5, 6, 7, X, 9, 10, 11, 12, 13, 14, 15, X, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, X, ...Now multiply 3 times ever overlined and crossed out number in the list. Do this sequentially from right to left crossing out each product before examining the next number. 3*2 is 6. Cross out 6.
_ _ 2, 3, X, 5, X, 7, X, 9, 10, 11, 12, 13, 14, 15, X, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, X, ...3*3 is 9. Cross out 9
_ _ 2, 3, X, 5, X, 7, X, X, 10, 11, 12, 13, 14, 15, X, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, X, ...3*4 is 12. Cross out 12.
_ _ 2, 3, X, 5, X, 7, X, X, 10, 11, X, 13, 14, 15, X, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, X, ...3*6 is 18. Cross out 18.
_ _ 2, 3, X, 5, X, 7, X, X, 10, 11, X, 13, 14, 15, X, 17, X, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, X, ...3*8 is 24. Cross out 24.
_ _ 2, 3, X, 5, X, 7, X, X, 10, 11, X, 13, 14, 15, X, 17, X, 19, 20, 21, 22, 23, X, 25, 26, 27, 28, 29, 30, 31, X, ...3*9 is 27. Cross out 27.
_ _ 2, 3, X, 5, X, 7, X, X, 10, 11, X, 13, 14, 15, X, 17, X, 19, 20, 21, 22, 23, X, 25, 26, X, 28, 29, 30, 31, X, ...3*12 is 36 which is not in our list. So we need to identify the first number that is both not overlined and not crossed out. This number is five. Cross out 5. As above, multiply 5 times every overlined or crossed out number in the list. Cross the new number out before finding the next number. This produces the list below.
_ _ _ 2, 3, X, 5, X, 7, X, X, X, 11, X, 13, 14, X, X, 17, X, 19, X, 21, 22, 23, X, X, 26, X, 28, 29, X, 31, X, ...Note that if the list went to 35, 35 would NOT be crossed out because 7 has not yet been identified as prime. You may have observed that at each step of the procedure we identify a new prime and all composite numbers that contain prime factors SMALLER than the new prime. This is NOT all numbers that contain the new prime as a factor. In the sieve of Erastothenes we identify ALL numbers that contain the new prime as a factor at each step.
Continue the process with 7.
_ _ _ _ 2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X, X, 17, X, 19, X, X, 22, 23, X, X, 26, X, X, 29, X, 31, X, ...Continue the process with 11.
_ _ _ _ __ 2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X, X, 17, X, 19, X, X, X, 23, X, X, 26, X, X, 29, X, 31, X, ...Continue the process with 13.
_ _ _ _ __ __ 2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X, X, 17, X, 19, X, X, X, 23, X, X, X, X, X, 29, X, 31, X, ...All of the remaining numbers are prime.
We need to provide evidence that the above sieve actually works. If the sieve does not work there are two ways in which it can fail. The first way is that it may fail to identify a number as prime. The second way is that it may identify a composite number as a prime.
It will not fail in the first way because all numbers crossed out are generated as the product of two numbers greater than one. Therefore all crossed out numbers are not prime.
Consider the second mode of failure. If it identifies a composite number as a prime then there must be a smallest composite number that it identifies as prime. Call such a number C. Equivalently we can say it fails to identify C as a composite.
The number C has a largest prime factor P and a factor greater than the number one and equal to C/P. But according to the first part of the proof it will identify P as prime. C/P is smaller than C and contains prime factors smaller than P. C/P cannot be prime since by the first part above all primes are identified and if C/P were prime then it would have been overlined. P*C/P would then have been crossed out. But if C/P is composite and was not identified as such then C is not the smallest composite number identified as being prime which is a contradiction.
Create a sequence counter that starts at 2:
Seq 2 3 4 5 6 7 8 . . .The first number generated by this counter is 2. Start a modulo-2 counter that runs in parallel with the sequence counter.
Seq Mod2 2 X 3 1 4 0 5 1 6 0 7 1 8 0 . . . . . .When the sequence counter is at 3, the modulo-2 counter contains a one. None of the modulo counters contain a zero so we can start a modulo-3 counter.
Seq Mod2 Mod3 2 X 3 1 X 4 0 1 5 1 2 6 0 0 7 1 1 8 0 2 . . . . . . . . .When the sequence counter is 4, the modulo-2 counter contains a zero. If any of the modulo counters contain a zero we cannot start a new modulo counter. But when the sequence counter is 5 none of the modulo counters contains a zero. Start a modulo-5 counter at the sequence number 5.
Seq Mod2 Mod3 Mod5 2 X 3 1 X 4 0 1 5 1 2 X 6 0 0 1 7 1 1 2 8 0 2 3 . . . . . . . . . . . .We can continue in this manner indefinitely starting a modulo counter for each new prime number. The table below illustrates this Prime Number Machine.
Seq 2 x 3 1x 4 01 5 12x 6 001 7 112x 8 0231 9 1042 10 0103 11 1214x 12 00251 13 11362x 14 024031 15 100142 16 011253 17 122364x 18 0034751 19 1145862x . . . . . .We have generated a picture in which the value in each counter is represented by a color. We call the picture the prime number cascade. It can be found at The Pictures of the Month
Otto Smith
1715 Gise St.
Port Townsend WA, 98368
(C)opyright 1995, Seven Seas Software Inc., MathVISION Inc.