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.