### re: Daily Challenge #7 - Factorial Decomposition VIEW POST

``````import Data.List
import qualified Data.Map.Strict as Map

primes :: [Int]
primes = filterPrime [2..]
where filterPrime (p : xs) = p : filterPrime [x | x <- xs, x `mod` p /= 0]

decomp :: Int -> Map.Map Int Int
decomp n =
if n == 1 || n `elem` lowerPrimes then Map.singleton n 1
else Map.filter (/= 0) \$ divide Nothing 0 n lowerPrimes Map.empty
where
lowerPrimes = takeWhile (<= n) primes
divide Nothing             _     1 _             factors = factors
divide (Just current)      count 1 _             factors = Map.insert current count factors
divide Nothing             _     n (p : ps)      factors = divide (Just p) 0 n ps factors
divide curr@(Just current) count n prim@(p : ps) factors =
case n `divMod` current of
(q, 0) -> divide curr (count + 1) q prim factors
_      -> divide (Just p) 0 n ps (Map.insert current count factors)

decompFactorial :: Int -> String
decompFactorial n = toString \$ foldl1 (Map.unionWith (+)) \$ map decomp [2..n]
where toString = intercalate " + " . Map.foldlWithKey (\acc k v -> (show k ++ "^" ++ show v) : acc) []
``````

The `decomp` function creates a `(factor, power)` map describing the decomposition of an integer. The `decompFactorial` function creates this decomposition for all integers from `2` to `n`, then merges the maps summing the values for each key. The result is then pretty printed.

code of conduct - report abuse  