Primes

The first Beercamp of the new year is coming up (I hope — nobody has volunteered to organise a venue yet) so I thought I'd start the year off with something not too hard. At BarCamp 2 I promised that I'd go into another one of the Google Treasure Hunt problems — this one centred on prime numbers.

I'm going to leave most of the problem aside for next time, just picking off a simple part of it for now:

The full problem involves the manipulation of long lists of prime numbers, so being able to generate a list of prime numbers is a good start. As an example, the first 5 prime numbers are:

2, 3, 5, 7, 11

It's possible to solve this with a very naïve implementation which will check if a number n is prime using O(n) divisions. Normally linear algorithms are quite good, but to have something that will solve the next parts of the problem fast enough that you won't get too bored waiting for it you'll really want something that is sub-linear. The real challenge here (and actually it isn't that hard once you spot it) is to find a way to test a number for primeness which doesn't involve testing the division of every number up to it — and skipping the even numbers is still O(n) I'm afraid :)