Posted on February 7, 2014
Finding Prime Factorisation
Here’s a small textbook excercise that I decided to turn into a haskell program:
-- | factorize1 function is an interface to factorize function
factorize1 :: (Integral b, RealFrac a) => a -> [b]
factorize1 n = map round $ factorize n 2
-- | factorize requires an index k (since we can't use variables)
factorize :: RealFrac a => a -> a -> [a]
factorize n k
| k >= n = n : []
| n `isDivisableBy` k = k : factorize (n/k) k
| n `isDivisableBy` k == False = factorize n (k+1)
And a small supporting function that returns True if the product is a full number, and False otherwise
isDivisableBy :: RealFrac a => a -> a -> Bool
isDivisableBy n m = let fullNumber = fromInteger $ round (n/m)
in (n/m) == fullNumber
Example output:
> factorize1 1000645
[5,29,67,103]
Hope you enjoyed it as I did :)
