First, the obligatory link to the problem description.

I found this problem to be more difficult than than previous two problems because I didn’t immediately have the insight into the problem that made it easy. Rather than think about what properties of the problem I could exploit, I instead started with the most obvious solution and foolishly wrote:

user> (defn factors-of [n]
        (filter #(zero? (rem n %)) (range 2 (+ 1 (/ n 2)))))
#'user/factors-of
user> (factors-of 60)
(2 3 4 5 6 10 12 15 20 30)
user> (defn prime? [n]
        (not-any? #(zero? (rem n %)) (range 2 (/ n 2))))
#'user/prime?
user> (map prime? (range 2 10))
(true true true true false true false false)
user> (filter prime? (factors-of 13195)) 
(5 7 13 29)
user> (filter prime? (factors-of 600851475143)) 
; Evaluation aborted.

Then I laughed to myself when I thought about how much unnecessary and redundant computation that style involved, decided I didn’t want to wait a gazillion years for the computation to finish, and killed the process.

Rethinking the problem, I settled on the second easiest thing for me to understand, which was to generate a list of primes first and then test if they are factors. As was discovered by Lou Franco in his 20 days of clojure blog series, you can easily spend entire days lost down the rabbit hole of efficient prime generation with lazy lists.

There will be more about making lazy prime generators in a later post. For now, let’s just use a suitable lazy prime number generator named primes provided by clojure-contrib. Once I had that, the problem became a snap to solve.

(use '[clojure.contrib.lazy-seqs :only (primes)])

(defn prime-factors-of [n]
  (filter #(zero? (rem n %)) (take-while #(> n (* % %)) primes)))    

(reduce max (prime-factors-of 600851475143)) 

Comparing with my solution with other people’s, I see that some clever people used a different algorithm to avoid having to write a lazy prime number generator. Also, they are smarter in a second way because they realized there is also no need to keep a list of every possible prime factor – only the largest one.

So all I can say is: kudos to you smart people out there who realized sequentially pulling out factors will result in only prime factors being found, regardless of multiplicity. My attempt at their factorization algorithm became the following ball of code.

(defn largest-prime-factor-of [num]
  (let [q (long (Math/sqrt num))           ; quadratic limit
        factor? (fn [nom den] (zero? (rem nom den)))] 
    (loop [n num
          d 2]
      (cond
       (> d q) n                           ; num itself must be prime
       (= n d) n                           ; n must be prime
       (factor? n d) (recur (/ n d) d)     ; factor d out of n
       true          (recur n (inc d)))))) ; else try again with bigger d

(largest-prime-factor-of 600851475143)