I know that the Sieve of Eratosthenes is a fast way to find all prime numbers in a given range. I noticed that one implementation of a sieve spends a lot of time marking multiples of small primes as composite. For example, it takes 1000 times as long to mark off all of the multiples of five as it takes to mark off the multiples of 5003. In addition, when it is marking off the multiples of larger primes, most of them are multiples of small primes. In fact, if it could skip over multiples of 2,3,5,7, and 11, the sieve would be about 5 times faster.
Can someone describe a way to make a sieve faster by not having to deal with multiples of the first few prime numbers? Don --
