f :: [Int] -> Map Int Int -> Int -> Map Int Int
f _ m 1 = m
f [] m _ = m
f (p:ps) m n =
  case n `divMod` p of
    (d, 0) -> f (p:ps) (M.alter count p m) d
    (_, _) -> f ps m n
  where count Nothing = Just 1
        count (Just x) = Just $ x + 1

factorize :: Int -> Map Int Int
factorize = f primes M.empty