[Haskell-cafe] Re: Genuine Eratosthenes sieve [Was: Optimization fun]

[Jens Blanck]

>
> The point about "Eratosthenes's sieve" is that it does not specify
> algorithmically how to find the next number to be crossed. It does not
> even define how to store (crossed) numbers, it stores them "on paper".


But , I believe that Eratosthenes's sieve does specify how to store numbers
and how to find the next to cross out.

This is how I remember it:

0 List the numbers from 2 onwards.
1 Take first uncrossed number, say p.
2 Cross every pth number from there on (crossed or not).
3 Repeat from 1.

That "crossed or not" appears above makes repeated filters very tricky. It
is trivial with a mutable array, but that is not the preferred way so one
needs to somehow merge the crossing out lists. I haven't looked at it
really, but being sorted lists I would have thought that this merger would
be easy without resorting to things like priority queues, could someone
point this out to me?

The above mayeasily be optimised to only listing odd numbers (still cross
out every pth number in the list), and much less importantly by starting
from whereever p*p is.

Jens
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070220/65a7ee05/attachment.htm