Clojure Prime Factors

walkerku about 1 hour later:

• • Simpler (to me), but also slower.

  • (defn factors [n] (map #(/ n %) (filter #(zero? (rem n %)) (range 1 (+ n 1)))))

  • (defn prime? [n]    (or (= n 2) (= 2 (count (take 3 (factors n))))))

  • (defn prime-factors [n]   (filter prime? (factors n)))

Colin Jones about 2 hours later:

• • Depends on what you find simple, right? :) Removing the Math/sqrt optimization might be simpler, but isn’t as efficient. In any case,here’s my take, which is basically the same, but has a few differences that I see as simplifications:

  • 1. Uses the loop construct rather than arity overloading, so clients of the function only have one set of arguments to choose.

  • 2. Uses / instead of quot if the candidate is a divisor.

  • 3. Extracts divisible-by? predicate.

  • 4. Squares the arguments instead of calling directly into Java with Math/sqrt. There’s no risk of overflow because of the way Clojure handles numbers, and this will work with the .NET implementation.

Steven Devijver 1 day later:

• • One liner:

• • (reduce (fn [primes number] (if (nil? (some (partial = 0) (map (partial mod number) primes))) (conj primes number) primes)) [2] (take 1000 (iterate inc 3)))

Julian Birch 2 days later:

• • At the risk of writing C# in Clojure:

• • (defn factors [n]      {:pre [(pos? n) (integer? n)]}     (loop [n n, s 2, a '()]         (if-let [f (->> ; find smallest factor                 (range s n)                  (take-while #(<= % (Math/sqrt n)))                 (filter #(zero? (rem n %)))                 first)]                           (recur (/ n f) f (conj a f)) ; factor found             (conj a n))))    ; n is prime