3 ms·
It is also dirt slow. This is just trial division, done in a lazy fashion. At least it is better than the one some haskellers call the sieve of erathostenes (i
by bjoli 7y ago
It is also dirt slow. This is just trial division, done in a lazy fashion.
At least it is better than the one some haskellers call the sieve of erathostenes (it isn't the sieve of erathostenes), which is so god-awful that I almost vomit every time I see it.
The real lazy sieve of erathostenes is a thing of wonder! There is a paper describing it called "the genuine sieve of erathostenes" and it can be found by googling.
- ahakki 7y agothis? sieve :: Integral a => a -> [a] sieve l = sieve' [2..l] [] where sieve' (p:ns) ps = sieve' (filter (\x -> rem x p /= 0) ns) (p : ps) sieve' [] ps = reverse ps
- bjoli 7y agoThe lazy sieve i have seen, taken from the paper mentioned in my post: primes = sieve [2..] sieve (p : xs) = p : sieve [x | x <− xs, x ‘mod‘ p > 0]