[Haskell-cafe] A tale of Project Euler

[Sebastian Sylvan]

On Nov 27, 2007 8:44 PM, Andrew Coppin <andrewcoppin at btinternet.com> wrote:
> Andrew Coppin wrote:
> > Also, I'm stuck with problem #10. (Find the sum of all primes less
> > than 1 million.) I've let the program run for well over 15 minutes,
> > and still no answer is forthcomming. It's implemented using the same
> > primes function as above, with a simple filter and sum. (The type has
> > to be changed to [Word64] to avoid overflowing the result though.) The
> > other guy claims to have a C solution that takes 12 ms. There's a hell
> > of a difference between 12 ms and over half an hour...(!) Clearly
> > something is horribly wrong here. Uh... help?
>
> I just let it run to completion. Took 25 minutes and 15 seconds to find
> the (correct) answer. I would have preferred it to take 12 ms...
>


FWIW the following code took 0.77s on my machine:

primes :: [Integer]
primes = 2 : filter (null . primeFactors) [3,5..]

primeFactors :: Integer-> [Integer]
primeFactors n = factor n primes
    where
        factor m (p:ps) | p*p > m        = []
                        | m `mod` p == 0 = p : factor (m `div` p) (p:ps)
                        | otherwise      = factor m ps


main = print ( sum ( takeWhile (< 1000000) primes ) )


-- 
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862