4
\$\begingroup\$

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))
\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

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)))))
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.