There is another optimization that can be done to the "Erathosthenes' Sieve" which has some interesting results.
Instead of ordering your numbers in the standard way order them as follows:
1 2 3 4 5 6
7 8 9 10 11 12
.
.
.
as you can see each row adds on 6. What this means is that you can eliminate the 2's,3's,4's and 6's column. (we can also eliminate the 1 - though not the column).
Additonally, examine what happens when you have to eliminate a number. Effectively we get two columns:
one is 5 + 6n, and the other is 7+6m.
Let's assume that we have found a prime in one of the columns. First off, you have to eliminate all the numbers in the same column that are multiples of this number. This is done easily by moving forward the size of the number in the same column.
In other words: if x + 6n is prime then : x + 6n + (x+6n)*i is not a prime (since it divides by x+6n).
The only other problem is eliminating cross-columns. Interestingly the 5's column cancels the 7's but the reverse ins't true (meaning that as one searches for higher and higher prime numbers they will be equal to 5+6n with growing probability).
let's take a look at the two columns (drawn out here as rows):
5 11 17 23 29 35 41 47 53
7 13 19 !25! 31 37 43 49 !55!
the 25 and 55 have to be cancelled by numbers in the 5's column.
what we see is the following:
we'll rebuild the table
_1 _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 33 34 35 36
37 38 39 40 41 42
43 44 45 46 47 48
49 50 51 52 53 54
55 56 57 58 59 60
61 62 63 64 65 66
what we see here is the following: for each row we move down we add on 6. therefore, if we start at the 5, and go down one row and left one column we get a number that divides by 5. if we were to start at the 11, then we would have to go down two rows (+12) and back 1. To get from 5 to 25 we have to move down 4 times, and left 4 times. Therefore the index is the same as the 5's + 4. looking at the 11, we go down twice for every move left, therefore we have to go down 8 times, and left four times.
this works because we index 5 with 1, and 11 with 2, etc: in other words working off a base of -1 + 6k. For C, we'd change this to 5+6(k-1) = 5 + 6k, so that 5 would have index 0.
But, to keep things simple we're going to go with 5 having index 1.
So we've got two arrays, one which represents -1+6n (5's column), and the other which is 1+6m (7's column).
If -1 + 6n is a prime number then 1+6(n (starting index) + 4*n (4 times we move n down and one over)) divides by it = 1+6(n+4n) = 1 + 6*5n.
Therefore, since we know that the number at index 5n divides by -1+6n, we also know that: 1+6*5n + i(-1+6n) divides by -1+6n and isn't prime.
So, we can mark off all those as not being prime either (note that moving forward by -1+6n is minimal. If you move any less than a whole increment the resulting number will not divide by -1+6n).
If we look at the 7's column, we see a similar thing. Go down 1 row (+6) and moving right (+1) yields a number which is divisible by 7.
Therefore for a number 1+6n which is prime, the number n rows down (+6n) and 1 column over (+1) will divide by it.
Therefore moving 4 rows over we get that if 1+6n is prime then:
5+6(n+ 4*n) divides by it = 5 + 6*5n
However, this number is divisible by 5!!!!!!!!!!!
Hence, if we first handle the case of 5, any primes found in the 7's column don't affect those in the 5's column.
So here's the algorithm:
two arrays one for -1 + 6n (5 is at index 1), one for 1 + 6m (7 is at index 1). The index of each array maps to n and m respectively. Alternately, you can use a regular sized array and remember that the index is one smaller than what is needed for calculating cancellations.
i <- 1.
Print out 2 as being prime, print out 3 as being prime.
1) in the 5's take the next number (index i). if it hasn't been marked go down the array by -1+6i steps tagging as you go. Mark 5n in the 7's array as not being prime, and go down that array by -1+6i steps tagging as you go. (if it has been marked, continue straight to 2)
2) in the 7's take the next number (index i). if it hasn't been marked go down the array by 1+6i steps tagging as you go.
3) i<- i+1. go to 1.
This will allow you to print out the primes in the correct order with no problems whatsoever.
I implemented this once, for any number of primes (millions, billions, etc). it works really quite well.
Let's say you're looking for the first 1 thousand primes.
You can easily hold that many in a 1000x2 array, where you save the index in one field, and whether it's in the 5 column or the 7's column in the other field (if you're sticky for space use two arrays, one of which can be a bit array. If you need to do a billion or so (or any amount that you don't have enough memory for) you'll have to use a file).
Let's assume that you're working in increments of 100.
go over the above algorithm saving the indeces of the primes as you go along. When you're array is filled flush it (reset to the blank case) add one to the counter and fix the numbers as needed. This step isn't hard. After the first pass you've got the indeces of the primes, now then, we want to use that knowledge to throw out the numbers which are multiples of them on the second pass. This is just simple arithmetic (for each index find the first number in each arrray to which it maps (this is an arithmetic calculation), and then eliminate the following numbers as necessary). Note that you have to do two sets of cancellations for indeces in the 5's column: one in the 5's column and one in the 7's.
In any case, even you decide to go for the simpler standard algorithm, you can still use the same trick of remembering which numbers you found to already be prime, and eliminate as needed.
