[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
where
-- 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
False
else
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,
Christos
More information about the Beginners
mailing list