# Project Euler #3

I'd like to have the code below reviewed on all aspects.

Task: Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

My solution

shared.clj

(ns shared)

(defn prime-seq []
((fn prime-seq-gen [s]
(cons (first s)
(lazy-seq (prime-seq-gen (filter #(not= 0 (mod % (first s))) (rest s))))))
(iterate inc 2)))

(defn first-prime-factor [n]
{:pre [(>= n 2)]}
(first (filter #(= 0 (mod n %)) (prime-seq))))

(defn prime-factors [n]
{:pre [(>= n 2)]}
(loop [n n s []]
(if (= n 1)
s
(recur (/ n (first-prime-factor n))
(conj s (first-prime-factor n))))))


problems/problem3.clj

(ns problems.problem3
(:require shared))

(defn largest-prime-factor [n]
(apply max (shared/prime-factors n)))

(println (largest-prime-factor 600851475143))


## 2 Answers

Your prime-seq function is cute indeed. A couple of minor niggles:

• You compute (first s) twice. No big deal, but destructuring avoids this, and might even be clearer.
• Give lazy-seq as much scope as possible for maximum laziness.

For my own benefit, I defined

(defn divides-by? [m n]
(zero? (mod m n)))


Using this, and taking the above into account, we get

(defn prime-seq []
((fn prime-seq-gen [[n & ns]]
(lazy-seq
(cons n
(prime-seq-gen (remove #(divides-by? % n) ns)))))
(iterate inc 2)))


Moving on, I don't like the way you use first-prime-factor, since it tries every prime from 2 on. I'd go for the prime factors directly, trying each one until it is no longer a factor. Something like ...

(defn prime-factors [n]
(loop [n n, ans [], candidates (prime-seq)]
(case n
1 ans
(let [candidates (drop-while #(not (divides-by? n %)) candidates)
divisor (first candidates)]
(recur (quot n divisor)
(conj ans divisor)
candidates)))))


... using quot instead of / for integer division. For example,

(prime-factors 24651)
;[3 3 3 11 83]


The biggest is the last:

(last (prime-factors 24651))
;83


Or, by starting with () instead of [], we accumulate the factors LIFO, so the biggest is the first.

Or we can adapt the function to retain only the last element:

(defn largest-prime-factor [n]
(loop [n n, ans 1, candidates (prime-seq)]
(case n
1 ans
(let [candidates (drop-while #(not (divides-by? n %)) candidates)
divisor (first candidates)]
(recur (quot n divisor)
divisor
candidates)))))


Earlier today I spent some time understanding how to write a lazy infinite seq for primes in clojure. It's on stackoverflow so I can't claim too much originality, though I didn't copy the actual code. It uses an algorithm found here, and is a variation on the sieve of eratosthenes:

https://web.archive.org/web/20150710134640/http://diditwith.net/2009/01/20/YAPESProblemSevenPart2.aspx

It will go forever, won't overflow -- the prime seq functions above top out after only a few thousand. One Euler problem requires finding the 10001st prime number, so the above functions won't work. Also, problem #10 requires 148,933 primes if you solve it with a list. The algorithm referenced above takes about one minute to find the millionth prime number on my machine, and finds the 10000th one in 300ms. It would be a valuable function to have for these problems IMO, especially given that it's infinite and lazy.