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 (recurnbr (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 …).

Nice to see others doing Project Euler in Clojure! I found it to be a good way to explore the language. Back around the 1.0 days, I put together a slightly different approach. I pushed it to a gist over on Github: https://gist.github.com/913636

The basic idea is that we can generate primes completely in advance because we know the stopping criteria, which we capture in a stop predicate passed to a primes generator. Once that machinery is in place, it’s easy to write a prime-factor method that walks the list of primes and tests to see if they’re a factor of a given number. We run that tail-recursively and accumulate the list of factors.

Clojure’s nice for this problem and problem 8 because it has really nice support for large numbers.

Cheers,