[Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was:Genuine Eratosthenes sieve)

[Melissa O'Neill]

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):

[(3,69),(5,70),(7,70),(11,121),(13,169),(17,289),(19,361),(23,529), 
(29,841),(31,961),(37,1369),(41,1681),(43,1849),(47,2209),(53,2809), 
(59,3481),(61,3721),(67,4489)]

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.

     Melissa.

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.