After discovering Project Euler Clojure in my previous post I took a stab at problem 003 – “Find the largest prime factor of the composite number 600851475143”. In the spirit of true learning I did not look at any posted solutions while writing mine.
The first bright idea was to use lazy sequence primes from clojure.contrib.lazy-seqs in reverse order and simply working down divide target number by decreasing prime number looking for zero remainder. Well, it turns out that since primes is infinite simple filtering doesn’t work. Below enters infinite loop and should eventually run out of memory, I think. I just killed the process.
user=> (use '[clojure.contrib.lazy-seqs :only (primes)]) nil user=> (filter #(= 0 (rem 600851475143 %)) primes) ; never came back...
After pondering some time I decided to abandon “primes in reverse order approach”. If I can not realize infinite lazy sequence, I can look for specific item using nth. Fast forward some time and here is the final solution.
1 (use '[clojure.contrib.lazy-seqs :only (primes)])
2
3 (defn max-fctr [target]
4 (loop [nbr target, idx 0, fctrs []]
5 (let [cp (nth primes idx), rmndr (rem nbr cp)]
6 (if (= 0 rmndr)
7 (recur (/ nbr cp) 0 (conj fctrs cp))
8 (if (> cp nbr)
9 (last fctrs)
10 (recur nbr (inc idx) fctrs))))))
11 (max-fctr 600851475143)
On line 3 I setup explicit recursion point. On line 5 I capture current prime (cp) from primes and compute reminder (rmndr). If reminder is zero we set target number to a larger factor as an optimization, reset primes index to zero and add smaller factor to an accumulating vector of primes. Otherwise, to terminate recursion we compare current prime to our target number and if it is greater return last found factor. If current prime is less, we recur with incremented index. On my laptop above runs in about 20 msecs.
Well it is time to check how above compares to other solutions at project euler’s site… Overall, not bad – my solution is on a shorter side and only the 2nd one that takes advantage of lazy primes. Please note that I did not compare performance of other solutions. The best solution IMHO is by mtgred followed by davirus which looses because it relies on external functions (eg. prime?). Interestingly the best solution has approach similar to mine and both shorter and faster (runs in about 800 microseconds on my laptop). Let me reproduce it here (I made it slightly more readable).
1 (defn prime-factors [n]
2 (let [f (some #(if (= 0 (rem n %)) %) primes)]
3 (if (= f n)
4 #{f}
5 (conj (prime-factors (/ n f)) f))))
6 (apply max (prime-factors 600851475143)
mtgred uses clever trick with implicit recursion which dispenses with loop/recur and accumulating vector of factors. Also, using some instead of nth eliminates need for index and, my guess, makes it faster. Since unordered set is used #{f} it requires (apply max …).
On Software and Life 