[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