And today I saw this link:
http://article.gmane.org/gmane.comp.lang.haskell.cafe/19470
It's a fairly clever implementation that doesn't actually do any modular division (which is cool, of course, because division, even just to get a remainder, is a relatively expensive operation). It also takes advantage of some Haskell-specific things like lazy evaluation, but I stole some ideas from it and wrote a version of my own that ends up being quite fast compared to the other implementations I was playing with.
The algorithms I've played with:
1) The simplest implementation of your algorithm in Common Lisp: build a list of odd integers from 3 to n, walk through it, picking off the head element then removing all multiples of that number. The primes to 1,000,000 took 3.7 seconds. The primes to 10,000,000 took 86.7 seconds.
2) The same algorithm, with some tricks to avoid consing (memory allocation, mostly because allocating memory just to throw it away can be slow): build a list of odd integers from 3 to n, walk through that list, removing multiples of the current element from later in the list by splicing together the non-multiple elements of the list (rewriting the pointers in the linked list, basically). The primes to 1,000,000 took 3.4 seconds. The primes to 10,000,000 took 80.4 seconds.
3) My "list primes up to n" function, which doesn't use the Sieve of Eratosthenes: check all odd integers from 3 to n for primality, collect the ones that are prime. The primes to 1,000,000 took 0.160 seconds. The primes to 10,000,000 took 23.6 seconds. (I precache the primality of all integers from 0 to 2^22, so when n=10^6, all prime testing is just table lookups. When n=10^7, it has to actually start doing work, so it gets slower.)
4) The algorithm with ideas stolen from the Haskell code: make an array of bits with indices from 0 to n, set all bits on, for each odd integer from 3 to n, if its bit in the array is still on, hit every multiple of that number (by iterative addition) in the array and turn its bit off, finally create a list of 2 plus all the odd numbers that still have their bits on. The primes to 1,000,000 took 0.076 seconds. The primes to 10,000,000 took 1.256 seconds. The primes to 100,000,000 took 13.8 seconds. The primes to 2^29 (max length of an array in my Common Lisp implementation) took 83.4 seconds.
You can see my code at