Generating primes in Haskell

Question

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

I'm not sure why this function doesn't seem to terminate, but I can see why it outputs only 1, isn't it because you filter out the prime numbers along with their derivatives? — Kimitsu Desu
– Kimitsu Desu, Commented Feb 5, 2013 at 9:05
I was intending to append the prime (i.e. the first number in the list) using the x: before the filter function, which was only acting on the rest of the list, xs. How would I do that? @KimitsuDesu — bennybdbc
– bennybdbc, Commented Feb 5, 2013 at 9:09
As a side note, this is not a sieve. It's simply a trial division prime generator. — ertes
– ertes, Commented Feb 5, 2013 at 10:53
BTW, you might want to check this great article if you care about performance latter on. The algorithm you are using is worse then trial division. — hugomg
– hugomg, Commented Feb 5, 2013 at 13:47

MathematicalOrchid · Accepted Answer · 2013-02-05 09:08:41Z

2

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

answered Feb 5, 2013 at 9:08

MathematicalOrchid

63.1k21 gold badges131 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

bennybdbc Over a year ago

I just tried using q mod x, and it resulted in the function terminating, but only returning [1]

MathematicalOrchid Over a year ago

Try passing it the list [2..20000] as input instead. I think the 1 step is filtering out everything.

Petr · Accepted Answer · 2013-02-05 09:13:48Z

2

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]

answered Feb 5, 2013 at 9:13

Petr

63.6k13 gold badges163 silver badges333 bronze badges

1 Comment

bennybdbc Over a year ago

Thankyou for this, its very helpful seeing good examples of Haskell code

Collectives™ on Stack Overflow

Generating primes in Haskell

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related