[Haskell-cafe] Optimization fun

[Lennart Augustsson]

There are many things that makes your code slow.
* The default for Haskell is to compute with Integer, not Int.  So  
that makes from Integral and floor very slow.
* foldl' is a bad choice, because it is too strict, you want to abort  
the loop as soon as possible.
* your take is really wrong.  The number of primes you need to take  
cannot be computed like that.  You want to take primes while the sqrt  
of x is larger than the prime.

Also, your code is not idiomatic Haskell.

Here's a different version:

primes :: [Int]
primes = 2:filter isPrime [3,5..]
     where isPrime x = all (\ y -> x `mod` y /= 0) $ takeWhile (\ p - 
 > p*p <= x) primes


On Feb 10, 2007, at 21:02 , Creighton Hogg wrote:

> primes = 2:(foldr (\x y -> if isPrime x then x:y else y) [] [3..])
>     where isPrime x = foldl' (\z y -> z && (if x `mod` y == 0 then  
> False else True)) True (take (floor $ sqrt $ fromIntegral x) primes)