[Haskell-cafe] factorising to prime numbers

[Dougal Stanton]

Hi folks,

I recently read in my copy of Concrete Mathematics the relationship
between prime factors powers and lcm/gcd functions. So I decided to
reimplement gcd and lcm the long way, for no other reason than because
I could.

If you look at the definition of 'powers' you'll note it's infinite. So
there's no easy way to take the product of this list, if I don't know
how many items to take from it.

Is there a better way to turn an integer N and a list of primes
[p1,p2,p3,...] into powers [c1,c2,c3,...] such that

N = product [p1^c1, p2^c2, p3^c3, ...]

If I'm missing something really obvious I'll be very grateful. I can't
really work out what kind of structure it should be. A map? fold?

D.


-- Concrete Mathematics
-- Graham, Knuth & Patashnuk

module Concrete where

import Data.List

-- the sieve of eratosthenes is a fairly simple way
-- to create a list of prime numbers
primes = 
    let primes' (n:ns) = n : primes' (filter (\v -> v `mod` n /= 0) ns)
    in primes' [2..]

-- how many of the prime p are in the unique factorisation
-- of the integer n?
f 0 _ = 0
f n p | n `mod` p == 0 = 1 + f (n `div` p) p
      | otherwise = 0

powers n = map (f n) primes

--gcd :: Integer -> Integer -> Integer
--gcd = f . map (uncurry min)

-- 
Dougal Stanton