On 11/27/07, Sebastian Sylvan <sebastian.sylvan@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.