99 Clojure Problems – 36: Determine the Prime Factors of a Given Positive Integer (2)

Construct a list containing the prime factors and their multiplicity. Alternately, use a map for the result.

Example

(deftest p36-prime-factors-multiplicity
  (is (= {3 2, 5 1, 7 1} (prime-factors-multiplicity 315) )))

Solution

If you have been following this series this problem might sound familiar. In fact it is just a slight variation on the combination of Problem 35 (prime factors) and Problem 10 (run-length encoding). I followed Phil Gold in using a map as the output format to make the problem a bit more interesting.

While you could reimplement the solution from scratch, I think it is good practice to reuse existing code. In this case all we have to do is call prime-factors on the input, run-length encode, reverse the individual pairs of primes and their multiplicity as required by the problem description. Turning it into a map is then just a matter of flattening the result and applying the assoc function to an empty map and our intermediate result. Try it yourself before you look at the code.

Read more about this series.