CODEWITHSUNDEEP
haskellprimes
bennybdbc
bennybdbc

Reputation: 1425

Generating primes in Haskell

I have been learning Haskell over the last few days, through Learn You A Haskell. I've been attempting to complete some Project Euler problems, some of which require primes. However the function I have written to try to generate some (in this case primes below 20000) isn't outputting correctly. When I run it, GHCi returns '[1, ' and seemingly doesn't terminate. The code I am using is:

sieve :: (Integral a) => a -> [a] -> [a]
sieve 20000 list = list
sieve n (x:xs) = sieve (n+1) $ x:(filter (\q -> q `mod` n /= 0) xs)

primesto20000 = sieve 2 [1..20000]

And then I am calling primesto20000. I understand that the function may be inefficient, I am mainly asking for help on syntactic/process errors that I must have made.
Thankyou

Upvotes: 0

Views: 1431

Answers (2)

Petr
Petr

Reputation: 63409

There are two problems in your code:

  • Because its time complexity (quadratic I guess), it doesn't finish in a reasonable time and it seems that it just hangs. If you replace 20000 with 200, it'll finish, but the result will be [1].
  • The other problem is that for each n you want to filter all numbers divisible by n that are larger than n. Without this condition, you filter n itself, which has the result that you filter out all numbers.

A corrected version could look like (with a parametrized limit):

limit :: Integral a => a
limit = 20000

sieve :: (Integral a) => a -> [a] -> [a]
sieve n list | n == limit
    = list
sieve n (x:xs)
    = sieve (n+1) $ x : (filter filt xs)
  where
    -- filter everything divisible by `n`, but not `n` itself.
    filt q = (q <= n) || (q `mod` n /= 0)

primesto20000 = sieve 2 [1..limit]

Upvotes: 2

MathematicalOrchid
MathematicalOrchid

Reputation: 62858

You're filtering out multiples of every number, not just prime numbers. You want to check divisibility by x, not by n. (In fact, I'm not sure you need n in the sieve function at all; just make your primesto20000 function generate the appropriate input list, and pass that.)

Upvotes: 2

Related Questions