*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 3

^{2}, and crossing off multiples of three (starting with 9) eliminates all remaining non-primes up until 5

^{2}, and crossing off all multiples of 5 (starting at 25) eliminates all remaining non-primes up until 7

^{2}, 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.

## 2 comments:

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

haveto 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.

Hooray for nerd confessions! It's OK if it's old hat - I mean, in terms of good ideas, it doesn't get

thatmuch 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!Post a Comment