Project Euler #3

Question

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))

Answer 1

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)))))

Answer 2

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.