# Project Euler in Clojure – Problem 3

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 2 can be found here.

Problem 3 of Project Euler is described as:

`What is the largest prime factor of the number 600851475143 ?`

For this problem, I needed to generate the prime factors of a number. In order to generate the prime factors, I decided to pul out the Uncle Bob’s (found here, here, here, and here) Prime Factors Kata and apply it to Clojure. By doing this kata, I test drove the result, and decided I would give Brian Marick’s Midje a shot and play with that some as well. The resulting tests are as follows.

```(ns project-euler.prime-factors-test
(:use clojure.test
midje.sweet
project-euler.core))

(defn mersenne [n]
(int (dec (Math/pow 2 n))))

(fact
(prime-factors-of 1) =&gt; []
(prime-factors-of 2) =&gt; 
(prime-factors-of 3) =&gt; 
(prime-factors-of 4) =&gt; [2 2]
(prime-factors-of 5) =&gt; 
(prime-factors-of 6) =&gt; [2 3]
(prime-factors-of 7) =&gt; 
(prime-factors-of 8) =&gt; [2 2 2]
(prime-factors-of 9) =&gt; [3 3]
(prime-factors-of 10) =&gt; [2 5]
(prime-factors-of 11) =&gt; 
(prime-factors-of 12) =&gt; [2 2 3]
(prime-factors-of 16) =&gt; [2 2 2 2]
(prime-factors-of 25) =&gt; [5 5]
(prime-factors-of (* 2 3 5 7 11 17 37)) =&gt; [2 3 5 7 11 17 37]
(prime-factors-of (mersenne 17)) =&gt; [(mersenne 17)])
```

The total solution to problem 3 is as follows, with the test driven function for generating the prime factors, is:

```(defn factors-starting-at [f n]
(cond (= n 1) []
(zero? (rem n f)) (cons f (factors-starting-at f (/ n f)))
:else (recur (inc f) n)))

(defn prime-factors-of [n]
(factors-starting-at 2 n))

(defn problem3 []
(reduce max (prime-factors-of 600851475143)))
```

The resulting function for prime-factors-of calls the recursive function factors-starting-at with the first factor of 2, and the number itself. The factors-starting-at returns an empty vector when n is one. When the factor is actually a factor of the number (zero? (rem n f)) the returned result is the factor cons’ed onto the result of calling factors-starting-at again with the same factor, and the number divided by that factor. Otherwise, we return the result of recur-ing with the same number and the factor incremented again.

The solution to problem 3 is actually very simple in Clojure after one generates the prime factors for a number. All that one has to do is reduce the sequence of prime factors with the function max to find the largest prime factor for the number 600851475143.

I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Updated**
Here is my approach to Problem 4 in Clojure.

–Proctor

## 6 thoughts on “Project Euler in Clojure – Problem 3”

1. kawas

Did you consider appling max to the factor collection instead of reduce ?

Seems to me that you could replace your 2 functions used to search prime factors for 1.
To me factor-starting-at does not encapsulate a generic behavior that need to be defined on its own.
A function with loop/recur and an accumulator (for example an hashset) will do the job and you got tail recursion as a bonus 😉

bye

1. Proctor

kawas,

I probably should have made the function factors-starting-at private by declaring it defn-, if my knowledge of Clojure is accurate. It was defined as a method to be able to get the tail call recursion on the :else case of the cond function. I would love to see a snippet of your function using loop/recur to see your approach to using this, as I would guess my approach is still a bit imperative in that sense.

As for the apply versus reduce call, I have done apply in some of the problems and reduce in others. If there is a good way to determine when to do one or the other I would love to hear that as well.

–Proctor

1. kawas

Hello,

To me, because of the 2nd line of factor-starting-at, the function may not be tail recursive.

The alternative using a loop/recur may look like this:
(defn prime-factors [n]
(loop [f 2 n n res []]
(cond
(<= n 1) res
(zero? (rem n f)) (recur f (quot n f) (conj res f))
:else (recur (inc f) n res))))

Note1: I've used (<= n 1) because the code fail on double precision arithmetic :
(prime-factors-of (Math/pow 2 59))

Note2: Seems like there is a bug using bignums too :
(prime-factors (bigint (bigdec (Math/pow 2 59))))

Cheers

1. Proctor

kawas,

Thanks for the update. I will have to play with your solution and those possible bugs. I am thinking I will even try again to see if I can’t get the function call in the second conditional (zero? (rem n f)) to use recur, and use what I did and what you gave me to better understand recur at the function level versus using recur in a loop.

–Proctor