Confusing performance results for prime

[Lulu of the Lotus-Eaters]

bokr at oz.net (Bengt Richter) wrote previously:
|In doing some testing of different but simple algorithms for getting a
|list of prime numbers

This general topic came up quite recently.  I myself wrote a bunch about
various data structures to cache primes and the like.  But that was all
fairly idle.

If you want to test primality quickly, using the sieve of erotosthenes
is pretty terrible.  At least if you only want to check relatively few
numbers, rather than assemble all the primes.  Orders of magnitude
better is to use Miller-Rabin pseudoprimality tests (well, complexity
orders really).

Pick the right algorithm before worrying about micro-optimizations.

Yours, Lulu...