CS + AM: Eratosthenes' Sieve

As mentioned earlier, I'm in an essentially Applied Math course through my Computer Science department, dealing with the history and applications of various algorithms.

On Tuesday, my class played (some more) with the Sieve of Eratosthenes, which is a quite interesting way to find prime numbers. There are two ways you can create the sieve. The first of which is starting from the number 2 above your second column. The second way, which is what my class was dealing with, is to only write odd numbers, starting at 1 and going to whatever threshold you'd like to stop at.

In class, we received a 15-column wide sieve, containing the odds from 1 to 1019, inclusive (we wanted to count the primes less than 1020). Now, by the definition in mathematics, 1 is not a prime. I won't explain that, since I don't know the details at the moment (I'll probably look at Wikipedia later for such things). Now, starting from the next number, 3, decide if it is a prime. As 3 is a prime, circle it and begin counting every n squares. Every third square will be divisible by this prime n. Cross out every one of these numbers.

So, after you have 3 circled, you should cross out 9, 15 and such before going down to the next row of numbers. But first, if you are using a number of columns divisible by 3, you should look at the squares directly below those which you have already circled and crossed out. If done correctly, every square in a straight line downwards will be divisible by three. You can cross out the rest of the column if this is the case. There will also be cases where you can have diagonal lines crossing squares out (which I believe happens with 7 on a 15-column sieve).

After you finish crossing out all those numbers divisible by 3, move on to the next number, 5. Five is a prime, so circle it and go to the square containing its square (the square containing n squared, or n^2). Cross this position out, then continue to cross out every nth item. Continue on through 7 and then look at 9. Note that we have already crossed it out, so go straight on to 11. This is a prime, so circle it and continue the process started with 3, 5 and 7. Continue this work until you reach a number whose square (^2) is greater than your last odd number. Once you get to that point, all 'composite' (i.e.- not prime) numbers should be crossed out. Now you can go through the Sieve to count up the number of primes in that set of numbers, then add 1.

The one is added because 2 is a prime, though it is not included in the Sieve because it is even. Interesting algorithm, no? If a current programmer, or have previous experience, think of how you could implement this algorithm in your language of choice (hint: try using a zero over each composite, rather than trying to use a blacklist).