A thing of beauty is a joy forever. Simple, fast, elegant. If I learn
any more from this list, someone is going to start charging me tuition! :)
Dan
[EMAIL PROTECTED] wrote:
G'day all.
Quoting Dan Weston <[EMAIL PROTECTED]>:
Why all the fuss? n! is in fact very easily *completely* factored into
prime numbers [...]
It's even easier than that.
primePowerOf :: Integer -> Integer -> Integer
primePowerOf n p
= (n - s p n) `div` (p-1)
where
s p 0 = 0
s p n = let (q,r) = n `divMod` p in s p q + r
factorisedFactorial :: Integer -> [(Integer,Integer)]
factorisedFactorial n = [ (p, primePowerOf n p) | p <- primesUpTo n ]
factorial :: Integer -> Integer
factorial = product . zipWith (^) . factorisedFactorial
(Implement primesUpTo using your favourite prime sieve.)
Manipulating prime factors like this is sometimes MUCH faster than
computing products for this kind of combinatorial work, because Integer
division is quite expensive.
Cheers,
Andrew Bromage
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
