Recently, I'm trying to solve some problems in project euler using haskell. When it came to problem 10, calculating the sum of all primes below 20000000, I try to write a program which can generate primes.<br>In my memory Eratosthenes is faster than just whether a number can be divided by the number less then the square root of it.<br>
Firstly, I wrote the following programs:<br><br>module Main where<br>isPrime x = isPrime' 3 x (round . sqrt. fromIntegral $ x)<br>isPrime' d target maxd<br> | d > maxd = True<br> | mod target d == 0 = False<br>
| otherwise = isPrime' (d + 2) target maxd<br><br>main = print $ (sum (filter isPrime [3,5..2000000]) + 2)<br><br>And it consume about 11s in my computer.<br>Then, I tried to figure out how to solve the problem by Eratosthenes, but failed. Later, I find a program implemented by others, meeting my purpose and I've used it to solve the problem:<br>
<br>primes :: [Int]<br>primes = primes' [2..]<br><br>primes' :: [Int] -> [Int]<br>primes' [] = []<br>primes' (n:ns) = n : primes' (filter (\v -> v `mod` n /= 0) ns)<br><br>solve x = sum $ primes' [2..x]<br>
<br>main = print $ solve 2000000<br><br>Well, although the code is beautiful, it is slow. Even waiting for a minute, no answer was printed.<br><br>In C version, Eratosthenes is faster than the method implemented in my earlier code, which only consume 0.3s(the earlier method consume 1.6s).<br>
<br>So I want to know, why Eratosthenes implemented in Haskell is slow than the ugly code implemented by me.<br>Could anyone tell me?<br><br><br>Thank you<br>Yi Cheng<br>