2010-10-09

Sieve

I have been learning Haskell for a mere two weeks in class, but am already quite delighted with it. Here is one of the toy programs I wrote today.




{-
sieve.hs, Haskell implementation of sieve of Eratosthenes:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

this program is somewhat sub-optimal--e.g., I find all the composite numbers to n * p, rather than n.
I blame the fact that
1. this is totally for fun
2. I'm still very n00b at Haskell
-}

doSieve n = [p | p <- [2, 3 .. n] , not (p `elem` (compositeNumb n 2))]

compositeNumb n p =
if n < p^2
then []
else ([p * mults | mults <- [2, 3.. n]]) ++ compositeNumb n (p + 1)

No comments: