[Haskell-cafe] Re: Code and Perf. Data for Prime Finders
(was:Genuine Eratosthenes sieve)
oneill at cs.hmc.edu
Sun Feb 25 14:37:39 EST 2007
Claus Reinke wrote:
> folklore3: merging the sieves, instead of stacking them as
> implicit thunks
Here's Claus's code:
primes3 = 2 : folklore3  [3,5..]
> folklore3 pns xs = x : folklore3 (insert (x,x*x) pns') xs'
> where (x,pns',xs') = sieve3 pns xs
> sieve3 ((p,n):pns) (x:xs) | x<n = (x,((p,n):pns),xs)
> | otherwise = sieve3 (insert (p,(n+p))
> pns) ([x|x>n]++xs)
> sieve3  (x:xs) = (x,,xs)
> insert (p,n)  = [(p,n)]
> insert (p,n) ((p',n'):pns) | n<=n' = (p,n):(p',n'):pns
> | otherwise = (p',n'):insert (p,n) pns
This isn't a variant of the "folklore sieve", it's actually the real
one! Let's take a look at ``pns'' at the 20th prime, having just
found that 67 is prime (we're about to discover that 71 is prime):
As you can see, 70 will be crossed off twice, once by the 5 iterator
and once by the iterator for 7. And we won't think about 11, 13,
etc. until they're needed.
This algorithm is doing pretty much exactly what mine does, except
that in mine I use a priority queue to represent this information.
In fact, with my most recent code, I'd only store (3,69), (5,70),
(7,70) in the priority queue and keep (11,121), (13,169), ...,
(67,4489) in a feeder queue so that I only use the power of the
priority queue when I need it.
P.S. Mine actually wouldn't have quite the same numbers, because I go
to a bit of trouble to skip numbers like 70 which will never actually
show up in the x:xs list.
More information about the Haskell-Cafe