## Wednesday, October 28, 2009

### 101 Interesting Things, part thirty: The Sieve of Eratosthenes

I frequently get bored at work, because being a quality consultant is not an interesting job to me on a day-to-day basis - it's new problems and challenges that I find interesting, and everything else is grunt-work. So when I've got absolutely nothing to do (much less anything new), I sit around and give myself problems to solve, such as finding a way to recognize a prime number generator if I saw it (and thus, by extension, how to design a prime number generator and also what that prime number generator would be). I sometimes find it useful to attack a problem visually, so I started writing numbers to see if any pattern jumped out at me once I had all the primes through 200 isolated in a picture.

I realized that, since prime numbers have no factors which are also integers, I could eliminate all the non-primes by crossing out all multiples of two (except two itself), then all the multiples of three (except three itself), and then things get interesting. You see, I don't need to cross off multiples of four, since I've already done that by crossing off multiples of two. Five is another prime number, so cross off every number ending in five or zero (except five itself), but six has already been taken care of, thanks to the joint efforts of two and three. Whoah.

I realized at some point that if you cross off all the multiples of a prime number from a list, it will eliminate all non-prime numbers until the square of the next prime (which will have been isolated by this very method in the immediately previous step). Crossing off multiples of two eliminates all primes until 32, and crossing off multiples of three (starting with 9) eliminates all remaining non-primes up until 52, and crossing off all multiples of 5 (starting at 25) eliminates all remaining non-primes up until 72, and so on and so forth. I then despaired because I was looking for a pattern that would use a non-eliminative method to determine what numbers don't fit any pattern; I was trying to describe a pattern of patternlessness as a pattern itself. Uh-oh.

The next day, I despaired some more, because I was walking through one of the campus buildings and saw a poster on the wall describing the sieve of Eratosthenes (easy mode). Shits! I mean, I could have sworn that there used to be a poster there showing how to make 3D hearts and smiley faces with mathematical equations, and decidedly not stealing this great idea I had and taking it back through time to ancient Greece! But no matter... I might have seen it the day before and forgotten about it, or learned it in my misspent youth and forgotten it, or merely come up with a good idea independently. Doesn't matter, the sieve is awesome and I know it. Now you know it, too - and knowing is half the battle.