reset password
Author Message
rabbott
Posts: 1649
Posted 09:32 Feb 16, 2019 |

Here are the three versions of the Sieve of Eratosthenes discussed in the previous post. They have been re-written to be similar and easier to understand.

sieve1 (p:ps) = p : sieve1 (filter (\n -> not (exclude n)) ps)
    where exclude n = n `mod` p == 0   

primes1 = 2 : sieve1 [3, 5 ..] 

{--
> take 1000 primes1
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101, ... , 7879,7883,7901,7907,7919]
(0.33 secs, 92,238,496 bytes)
--}


sieve2 (p:ps) = p : sieve2 (filter (\n -> not (exclude n)) ps)
    where exclude n = n >= p*p && n `mod` p == 0

primes2 = 2 : sieve2 [3, 5 ..] 

{--
> take 1000 primes2
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101, ... , 7879,7883,7901,7907,7919]
(0.41 secs, 162,026,024 bytes)
--}


sieve3 (p:ps) = p : sieve3 (filter (\n -> not (exclude n)) ps)
    where exclude n = let excludedStream = [p*p, p*(p+1) ..]
                                        excludedSet = takeWhile (<= n) excludedStream
                                   in n `elem` excludedSet

primes3 = 2 : sieve3 [3, 5 ..] 

{--
> take 1000 primes3
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101, ... , 7879,7883,7901,7907,7919]
(2.51 secs, 1,680,636,440 bytes)
--}


As you can see, sieve1 and sieve2 both compute 1,000 primes in less than 0.5 sec. sieve3 takes 2.5 sec.

Last edited by rabbott at 10:07 Feb 16, 2019.
rabbott
Posts: 1649
Posted 09:55 Feb 16, 2019 |

The preceding uses sieves discussed early in O'Neill's paper. I didn't read the entire thing, but at the end he discusses a "wheel" approach to eliminating numbers from the initial stream.

wheel2357 =  2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:4:8
            :6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel2357
spin (x:xs) n = n : spin xs (n + x)
primes4 = 2 : 3 : 5 : 7 : sieve1 (spin wheel2357 11)

{--
> take 1000 primes4
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101, ... , 7879,7883,7901,7907,7919]
(0.47 secs, 120,345,440 bytes)
--}

sieve4 ran slower than sieve2 (which ran slower than sieve1) but still under 0.5 sec for 1000 primes.

Last edited by rabbott at 10:09 Feb 16, 2019.