In today’s Programming Praxis exercise, our goal is to implement the Sieve of Euler to generate primes. Let’s get started, shall we?
Some imports:
import Data.List.Ordered import Data.Time.Clock
Euler’s sieve is pretty simple: just filter out all remaining multiples of each successive prime number. We add the minor optimization of only considering odd numbers.
primes_euler :: [Integer] primes_euler = 2 : euler [3,5..] where euler ~(x:xs) = x : euler (minus xs $ map (* x) (x:xs))
To compare, we use the Sieve of Eratosthenes implementation found here:
primes_eratosthenes :: [Integer] primes_eratosthenes = 2 : 3 : sieve (tail primes_eratosthenes) 3 [] where sieve ~(p:ps) x fs = let q=p*p in foldr (flip minus) [x+2,x+4..q-2] [[y+s,y+2*s..q] | (s,y) <- fs] ++ sieve ps q ((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs])
A quick and dirty benchmarking function:
benchPrimes :: Num a => [a] -> IO () benchPrimes f = do start <- getCurrentTime print . sum $ take 10000 f print . flip diffUTCTime start =<< getCurrentTime
Time to run the benchmarks.
main :: IO () main = do benchPrimes primes_eratosthenes benchPrimes primes_euler
The sieve of Eratosthenes runs in about 0.02 seconds, while Euler’s sieve takes around 6.6 seconds, which means this implementation of Euler’s Sieve is about 300-400 times slower. Clearly you don’t want to use this version in practice.