[Haskell-cafe] A tale of Project Euler
Olivier Boudry
olivier.boudry at gmail.com
Tue Nov 27 16:28:35 EST 2007
On 11/27/07, Sebastian Sylvan <sebastian.sylvan at gmail.com> wrote:
>
> That is indeed a nice and clear version that's pretty fast. It's
> basically the same as the C version except "backwards" (i.e. examine a
> number and work backwards through its divisors, rather than filling in
> a "map" of all multiples of a known prime).
> Let me suggest the following slight modification (primeFactors in your
> version doesn't actually return prime factors - it returns prime
> factors *or* a list of just the number itself),
>
> 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
>
>
> This is roughly 35% faster on my machine with GHC 6.7.20070730 too,
> but the point wasn't to make it faster, but clearer.
> --
> Sebastian Sylvan
> +44(0)7857-300802
> UIN: 44640862
>
Great remark, it's even simpler like this.
By the way I just found the article I stole this algorithm from:
http://www.haskell.org/haskellwiki/99_questions/31_to_41 last one in problem
35.
Cheers,
Olivier.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071127/4ee9bf14/attachment-0001.htm
More information about the Haskell-Cafe
mailing list