Number factorization in clojure

Question

I'm just a Clojure noob (started learning yesterday). Here is my helloworld program. It factorizes number into primes. Do you have any comments? How could I make this code cleaner and shorter? Maybe I can deduplicate some things?

(defn lazy-primes
  ([] (cons 2 (lazy-seq (lazy-primes 3  [ 2 ]))))
  ([current calculated-primes]
   (loop [ [first-prime & rest-primes] calculated-primes]
     (if (> (* first-prime first-prime) current)
       (cons current (lazy-seq (lazy-primes
                                (inc current)
                                (conj calculated-primes current))))
       (if (= 0 (mod current first-prime))
         (lazy-seq (lazy-primes (inc current) calculated-primes))
         (recur rest-primes))))))

(defn factorize
  ([num] (factorize num '(1) (lazy-primes)))
  ([num acc primes]
   (if (= num 1) acc
       (loop [ [head & rest] primes ]
         (if (= 0 (mod num head))
           (factorize (/ num head) (cons head acc) primes)
           (recur rest))))))

Answer 1

Wow! If this is you after one day, we hope for great things.

However, you can make your program simpler. Let's start with factorize. It has a couple of defects:

• It uses proper recursion where tail recursion with recur would suffice. So it would overflow the stack for a number having too many factors. However, since it uses long arithmetic, no number is big enough to do this.
• Each recursive call retries all the primes that have failed to be factors.

You can do it with a single loop if you exhaust each prime factor as you go:

(defn factorize [num]
  (loop [num num, acc [1], primes (lazy-primes)]
    (if (= num 1)
      acc
      (let [factor (first primes)]
        (if (= 0 (mod num factor))
          (recur (quot num factor) (conj acc factor) primes)
          (recur num acc (rest primes)))))))

Now let's look at lazy-primes. While sticking to your algorithm ...

• We can simplify the base case - the one with no arguments.
• You produce a lazy sequence level for every number tested. We can use recur to short-circuit tail recursion for all the numbers that fail to be prime.
• We can use take-while, map, and not-any? to express the prime testing more clearly (though it will run slower). Because these are lazy, we don't do any redundant testing.

The result is

(defn lazy-primes
  ([] (lazy-primes 2 []))
  ([current known-primes]
    (let [factors (take-while #(<= (* % %) current) known-primes)
          remainders (map #(mod current %) factors)]
      (if (not-any? zero? remainders)
        (lazy-seq (cons
                    current
                    (lazy-primes (inc current) (conj known-primes current))))
        (recur (inc current) known-primes)))))

A couple of arbitrary changes:

• I've used the abbreviated #(...) function syntax.
• I renamed calculated-primes to known-primes.

---

Edited to correct an erroneous comment.

Answer 2

Based on @Thumbnail answer there is still one little improvement, which leads to about twice increasing of performance: There is no prime numbers which is even we can just increment next value by two instead of one. So:

(defn lazy-primes
  ([] (cons 2 (lazy-primes 3 [])))
  ([current known-primes]
   (let [factors (take-while #(<= (*' % %) current) known-primes)]
     (if (not-any? #(zero? (mod current %)) factors)
       (lazy-seq (cons current
                       (lazy-primes (+' current 2) (conj known-primes current))))
       (recur (+' current 2) known-primes)))))

I also use *' operator instead of * because the prime numbers could be extremly large, so we need a large math here, but it's up to You.

Also, I removed on extra call, which also increase perfomance, not much - but worth it

So, little test results:

(time (last (take 10001 (old-lazy-primes))))

"Elapsed time: 37620.542326 msecs"

(time (last (take 10001 (lazy-primes))))

"Elapsed time: 18385.229566 msecs"

(time (last (take 10001 (lazy-primes)))) ;;without extra call

"Elapsed time: 11152.063344 msecs"

Yep, now it's faster triple as much.

UPDATE I removed the let expression gives a huge boost!

(defn lazy-primes
  ([] (cons 2 (lazy-primes 3 [])))
  ([current known-primes]
     (if (not-any? #(zero? (mod current %)) 
                   (take-while #(<= (*' % %) current) known-primes))
       (lazy-seq (cons current
                       (lazy-primes 
                        (+' current 2) 
                        (conj known-primes current))))
       (recur (+' current 2) known-primes))))

So let's test:

(time (last (take 10001 (lazy-primes))))

"Elapsed time: 4535.442412 msecs"

It's because of how not-any works. If this function on some point find that predicate for some value is false - just returns true and assuming that take-while is lazy... here we go! On my modern computer this function takes ~300 msec to count 10001 prime number.