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.


That Guy Montag said...

This is where I get sad and admit that one of my great joys when I'm bored is prime factoring bus numbers; Did you know that 343 is 7 cubed? When I'm super-duper bored I get a telephone number off a board but that only works if it's sort of hyper-even and I can halve it several times super quick. Having said that, one of the tricks you have to remember is that when testing a new integer, only test up to prime with the nearest square.

It also means this is like, totally old hat.

D said...

Hooray for nerd confessions! It's OK if it's old hat - I mean, in terms of good ideas, it doesn't get that much older than ancient Greece. But then, I didn't hear about it for some two-dozen years, and it's still an interesting thing in its own right. Anyway, thanks for the comment!