[Haskell-cafe] A tale of Project Euler

Kalman Noel kalman.noel at bluebottle.com
Wed Nov 28 07:12:28 EST 2007

```Sebastian Sylvan:
> 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

Your definition gives a strange meaning to primeFactors. I'd want that for all
n,  product (primeFactors n) == n.  I think this law holds for the code posted
by Olivier. Of course I'd beautify his definition slightly by writing

primes = 2 : filter isPrime [3,5..]

isPrime = null . drop 1 . primeFactors

primeFactors n | n >= 2 = factor primes n

factor pr@(p:ps) n
| p*p > n   = [n]
| r == 0    = p : factor pr q
| otherwise = factor ps n
where (q,r) = quotRem n p

Kalman

----------------------------------------------------------------------
Get a free email account with anti spam protection.
http://www.bluebottle.com/tag/2

```