He is how I did it:
I used 48 parallel sieves, one for each value in the range 0..210
which is not divisible by 2,3,5, or 7. If those numbers are store in
A[48]={1,11,13.17,19,23,...}, then the Nth bit in sieve S represents
the value N*210+A[S]. When a new prime P is encountered, you need to
find the first place in each of the 48 sieves where it will be
encountered. That will be the smallest value V > P^2 where V%210=A[S].
Then to process a sieve you take steps of size 210*P. This is about
four times faster than using a single sieve. It could be extended to
include multiples of 11, but I didn't do that.
Don
On Dec 7, 4:14 pm, Don <[email protected]> wrote:
> 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
--
