7 March 2010

Project Euler Problem 3 in Clojure - part 2

So the solution in part 1 was no good - it took half an hour to run. I spent a while trying and failing to make a lazy, purely functional version but after talking to Ed about his solution I came up with this, which runs in about 500msec :

(defn factor? [big small]
  (zero? (mod big small)))

(defn prime? [n]
  (not-any? #(factor? n %) (range 2 n)))

(defn primes []
  (filter #(prime? %) (iterate inc 2)))

(defn prime-factors [n]
  (let [factors (atom ())]
    (last
     (for [candidate (primes) :while (< (apply * @factors) n)]
       (if (factor? n candidate)
      (swap! factors conj candidate))))))

(defn solve []
  (first (prime-factors 600851475143)))

No comments:

Post a Comment