[Haskell-cafe] haskell.org

Ertugrul Söylemez ertesx at gmx.de
Tue Apr 21 01:11:45 UTC 2015


>> I'd like to note that the prime "sieve" example that is sitting at
>> the top of the homepage is not a real sieve [...]
>
> My understanding is that it *is* a sieve, just not the Sieve of
> Eratosthenes (because it's a bit hard to fit that into that small
> little sample box up the top of the page :p).

The main characteristic of a sieve is that it does not divide and that
it eliminates all multiples of a prime without a test.  Check one bit,
eliminate many.

In general if you see any of `mod`, `div` and friends, then it's very
unlikely to be a sieve.  The only real advantage of the example is that
it uses shared primes to use trial division only against primes (instead
of probable primes).  This gives a slight speedup at the expense of
needing a lot of memory.


Greets,
Ertugrul
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 472 bytes
Desc: not available
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150421/61433aa4/attachment-0001.sig>


More information about the Haskell-Cafe mailing list