I have just invented (It's probably been done by many different people in the last few thousand years, but I made it up myself this morning) an algorithm for generating a list of the first n prime numbers.

I start the list by supplying the first four terms, 3, 5, 7 and 11 (I'm ignoring 2) and when adding another to the list, I just grab the last term and add two. Then I try to divide the new number (x) by every prime in the list that comes before (and including) the square root of x.

It seems to be an efficient algorithm, apart from the fact that it only works if you have the entire list of primes up to the current term. So finding the 466428827442th term in the series would require serious RAM!

Does anyone know a faster way of generating say the first 1000 primes?

It's currently running on my Palm IIIx in PocketC. In terms of speed, it takes (-0.00002536n^3 + 0.03n^2 + 3.966n - 37.655) units of time to calculate n terms.