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) =>  (prime-factors-of 2) =>  (prime-factors-of 3) =>  (prime-factors-of 4) => [2 2] (prime-factors-of 5) =>  (prime-factors-of 6) => [2 3] (prime-factors-of 7) =>  (prime-factors-of 8) => [2 2 2] (prime-factors-of 9) => [3 3] (prime-factors-of 10) => [2 5] (prime-factors-of 11) =>  (prime-factors-of 12) => [2 2 3] (prime-factors-of 16) => [2 2 2 2] (prime-factors-of 25) => [5 5] (prime-factors-of (* 2 3 5 7 11 17 37)) => [2 3 5 7 11 17 37] (prime-factors-of (mersenne 17)) => [(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.
Here is my approach to Problem 4 in Clojure.