Prime Sieve in Haskell

user_1569960 0
Viewed 11729

I'm very new to Haskell and I'm just trying to find the sum of the first 2 million primes. I'm trying to generate the primes using a sieve (I think the sieve of Eratosthenes?), but it's really really slow and I don't know why. Here is my code. 

sieve (x:xs) = x:(sieve $ filter (\a -> a `mod` x /= 0) xs)
ans = sum $ takeWhile (<2000000) (sieve [2..])

Thanks in advance.

sieve-of-eratosthenes primes time-complexity haskell performance
6 Answers

A simple way to implement the genuine sieve of Eratosthenes in Haskell is to iteratively zipWith over a list of Boolean values signifying whether the corresponding number is prime:

primes :: Int -> [Int]
primes n = [x | (x, prime) <- zip [2..n] $
                  sieve (ceiling . sqrt $ fromIntegral n)
              , prime]
    where 
    sieve 1 = repeat True
    sieve n = zipWith (&&) (filt n) (sieve (n - 1))
    filt n = replicate (n - 1) True
             ++ (tail . cycle $ False :
                  replicate (n - 1) True)

Now, primes n gives the list of the first n primes.

user_63581820
Related