99 Clojure Problems – 35: Determine the Prime Factors of a Given Positive Integer

Example

(deftest p35-prime-factors
  (is (= '(3 3 5 7) (prime-factors 315))))

Solution

If you have ever done the "Prime Factors Kata" the solution to this problem is probably already in your muscle memory. One reason why this problem works well as an exercise is that there exists a very simple solution to it. In fact the solution can be expressed in just a few lines of code (in almost any language).

This simplest approach is to do trial division with increasing positive integers. You don't even have to bother checking for primality as things just fall into place: dividing by two for example effectively "eliminates" all multiples of two, in the sense that the next successful division can only happen with a number that is not a multiple of two. You do quite a lot of unnecessary divisions in the process though.

In my Clojure solution I chose to calculate a lazy (memoized) sequence of primes first and then do trial division using primes only. This reduces the number of divisions you have to do, assuming the primes are already calculated.

As long as your number is divisible by one of the small primes and does not have too many digits, trial division might be sufficient. For anything else you have to start looking at things like the general number field sieve.

Read more about this series.