# Efficient sieve of erastothenes, for solving project euler problem #10? Classic List Threaded 5 messages Open this post in threaded view
|

## Efficient sieve of erastothenes, for solving project euler problem #10?

 Hello all, I'm attempting to learn Haskell by going through the project euler problems. Number 10, http://projecteuler.net/index.php?section=problems&id=10 , involves summing prime numbers. It's easy in terms of coding something up that works, but I'm having a lot of trouble getting decent performance. I've learned a reasonable amount of ML at uni but Haskell is the first lazy language I've used.. I think the inefficiency is possibly due to the laziness but I'm not positive. I'd love if someone could show me how to do this in Haskell somewhere near as fast as C - at the moment I have a C version which runs in about a tenth of a second ( http://github.com/malcster/project-euler-solutions--c-/tree/master/10.c). My haskell attempts are http://github.com/malcster/project-euler-solutions/tree/master/10better.hs(using the sieve) and http://github.com/malcster/project-euler-solutions/tree/master/10.hs(using possibly an even worse method, but seems to be a bit faster). If anyone could point out any neat strictness annotations or anything else I could put in, that would be cool. Cheers, Malcolm
Open this post in threaded view
|

## Efficient sieve of erastothenes, for solving project euler problem #10?

 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
Open this post in threaded view
|

## Efficient sieve of erastothenes, for solving project euler problem #10?

 In reply to this post by Malcolm Reynolds On 11/23/2008, "Malcolm Reynolds" <[hidden email]> wrote: >Hello all, > >I'm attempting to learn Haskell by going through the project euler >problems. Number 10, >http://projecteuler.net/index.php?section=problems&id=10 , involves >summing prime numbers. It's easy in terms of coding something up that >works, but I'm having a lot of trouble getting decent performance. >I've learned a reasonable amount of ML at uni but Haskell is the first >lazy language I've used.. I think the inefficiency is possibly due to >the laziness but I'm not positive. > >I'd love if someone could show me how to do this in Haskell somewhere >near as fast as C - at the moment I have a C version which runs in >about a tenth of a second ( >http://github.com/malcster/project-euler-solutions--c-/tree/master/10.c>). My haskell attempts are >http://github.com/malcster/project-euler-solutions/tree/master/10better.hs>(using the sieve) and >http://github.com/malcster/project-euler-solutions/tree/master/10.hs>(using possibly an even worse method, but seems to be a bit faster). > >If anyone could point out any neat strictness annotations or anything >else I could put in, that would be cool. > >Cheers, > >Malcolm Hi Malcom, I have a solution to Project Euler problem #10 that runs in 7.3 seconds on my computer when compiled with -O2.  I am neither a math expert nor a Haskell expert, so others may be able to offer a better solution. module PE010 where import ProjectEuler(primes2) main = putStrLn output output = show result result = sum \$ takeWhile (\x -> x < 2000000) primes2 -- This is the relevant stuff from ProjectEuler.hs primes2 :: [Integer] primes2 = getPrime [] primeCandidates where     getPrime :: [Integer] -> [Integer] -> [Integer]     getPrime ls (x:xs) = let maxDiv = floor \$ sqrt \$ fromIntegral x in         if isDivisibleByAny (takeWhile (\n -> n <= maxDiv) ls) x         then getPrime ls xs         else x : getPrime (ls ++ [x]) xs primeCandidates = 2 : (oddsFrom 3) oddsFrom n     | odd n     = [n, n+2 ..]     | otherwise = [n+1, n+3 ..] isDivisibleByAny ls n = or \$ map (\d -> n `mod` d == 0) ls I didn't get a chance to look at your version, but obviously, 7.3 seconds is a lot slower than the 0.1 seconds you saw with your C version.