Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Prime factors Kata in Clojure
(ns prime-factors-test
(:use clojure.test midje.sweet))
(defn factors-starting-at [f n]
(cond
(> f (Math/sqrt n)) (if (= n 1) [] [n])
(= 0 (mod n f)) (cons f (factors-starting-at f (/ n f)))
:else (recur (inc f) n)))
(defn prime-factors-of [n]
(factors-starting-at 2 n))
(defn mersenne [n]
(int (dec (Math/pow 2 n))))
(deftest prime-factors
(fact (prime-factors-of 1) => [])
(fact (prime-factors-of 2) => [2])
(fact (prime-factors-of 3) => [3])
(fact (prime-factors-of 4) => [2 2])
(fact (prime-factors-of 5) => [5])
(fact (prime-factors-of 6) => [2 3])
(fact (prime-factors-of 7) => [7])
(fact (prime-factors-of 8) => [2 2 2])
(fact (prime-factors-of 9) => [3 3])
(fact (prime-factors-of 10) => [2 5])
(fact (prime-factors-of 12) => [2 2 3])
(fact (prime-factors-of 18) => [2 3 3])
(fact (prime-factors-of 25) => [5 5])
(fact (prime-factors-of 1369) => [37 37])
(fact (prime-factors-of (* 2 3 5 7 11 17 37)) => [2 3 5 7 11 17 37])
(fact (prime-factors-of (mersenne 17)) => [(mersenne 17)])
(fact (prime-factors-of (mersenne 19)) => [(mersenne 19)])
(fact (prime-factors-of (mersenne 31)) => [(mersenne 31)])
)
(run-tests)
@marvinthepa

This comment has been minimized.

Copy link

@marvinthepa marvinthepa commented Oct 24, 2010

I would use (zero? foo) instead of (= 0 foo). IMVHO it's more readable, and according to Rich Hickey it also performs better.

I would also be interested what you think about the non-stack-smashing version:

(defn factors-starting-at
  ([f n] (factors-starting-at f n []))
  ([f n result]
    (cond
      (> f (Math/sqrt n)) (if (= n 1) [] (conj result n))
      (zero? (mod n f)) (recur f (/ n f) (conj result f))
      :else (recur (inc f) n result))))

Does the extra argument hurt readability so bad that the non-tail-recursive version should be preferred for small numbers?

@unclebob

This comment has been minimized.

Copy link
Owner Author

@unclebob unclebob commented Oct 25, 2010

Good point on the (zero?), I had forgotten about that.

I chose the non-tail version because it only pushes the stack for prime factors that are repeated. So it could blow the stack for n**b where b is very large; but for most numbers it's pretty safe.

In general, though, tail-recursion should be preferred (of course) despite the extra arg.

@hoodja

This comment has been minimized.

Copy link

@hoodja hoodja commented Feb 28, 2012

Hi @unclebob,

I was attempting a version that didn't require the call-out to factors-starting-at, but instead applied a default starting factor. I came up with the following:
(I'm not using (cond), which is way neater; instead what is below reflects the structure of your original PrimeFactors kata in java)

(defn prime-factors-of
  ([n] (prime-factors-of 2 n))
  ([f n]
    (if (> n 1)
      (if (= 0 (mod n f))
        (cons f (prime-factors-of f (/ n f)))
        (recur (inc f) n)
      )
      ()
    )
  )
)

What is your opinion of the default value form versus extracting the factors-of function? I'm on the fence - SRP and clear names versus the simplicity of a single recursive call.

@unclebob

This comment has been minimized.

Copy link
Owner Author

@unclebob unclebob commented Feb 28, 2012

@marvinthepa

This comment has been minimized.

Copy link

@marvinthepa marvinthepa commented Feb 29, 2012

@hoodja: although it might seem strange when seen from a curly-brace-language-background, lispers like to put all closing parens on a single line (they feel lonely otherwise):

(defn prime-factors-of
  ([n] (prime-factors-of 2 n))
  ([f n]
    (if (> n 1)
      (if (= 0 (mod n f))
        (cons f (prime-factors-of f (/ n f)))
        (recur (inc f) n))
      [])))

I replaced () by [] to make the empty list stand out more clearly from all those parens.

To repeat my comment from above: (zero? num) is more readable than (= 0 num) IMHO, and it also has performance benefits (nice combo).

@unclebob:
I think that you really need an extra (accumulator) argument to make the function tail-recursive. But I'd be delighted if you can prove me wrong!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment