[Haskell-cafe] A tale of Project Euler
Sebastian Sylvan
sebastian.sylvan at gmail.com
Tue Nov 27 16:18:13 EST 2007
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
More information about the Haskell-Cafe
mailing list