[Haskell-beginners] Efficient sieve of erastothenes, for solving project euler problem #10?

Christos Chryssochoidis c.chryssochoidis at gmail.com
Sun Nov 23 19:32:52 EST 2008

Sorry, I pressed inadvertently the "send" button... The previous code
has some typos... :-)

The code is this:
isPrime :: Integer -> Bool
isPrime n = isPrimeAux n 2
      -- First param is the number to be tested
      -- for primality. Second param the current
      -- divisor.
      isPrimeAux :: Integer -> Integer -> Bool
      isPrimeAux n k
          | fromIntegral k > sqrt (fromIntegral n) = True
          | otherwise  = if n `mod` k == 0 then
                             isPrimeAux n (k+1)

main :: IO ()
main = print $ sum $ filter isPrime [2..1999999]

I compiled the code with "ghc --make prob10.hs", and although it
wasn't lightning fast I got the answer after a little less than a
minute on my system.

Hope it helped,


More information about the Beginners mailing list