Clojure Prime Factorization Sieve

prime-factorize.clj

;; Prime factorize all numbers in the range [2 100,000]

;; Naive, no sieve
(def prime-seq
  (concat
   [2 3 5 7]
   (lazy-seq
    (let [primes-from (fn primes-from
                        [n [f & r]]
                        (if (some #(zero? (rem n %))
                                  (take-while #(<= (* % %) n) prime-seq))
                          (recur (+ n f) r)
                          (lazy-seq (cons n (primes-from (+ n f) r)))))
          wheel       (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6  4  2
                              6 4 6 8 4 2 4 2 4 8 6 4 6 2  4  6
                              2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])]
      (primes-from 11 wheel)))))

(defn prime-factorize
  [x]
  (loop [x  (long x)
         ps prime-seq
         fs (list)]
    (let [p (long (first ps))]
      (if (> (* p p) x)
        (if (< 1 x)
          (cons x fs)
          (into [] (reverse fs)))
        (if (zero? (rem x p))
          (recur (quot x p) ps (cons p fs))
          (recur x (rest ps) fs))))))

(criterium/quick-bench
  (doall
    (map prime-factorize (range 2 100001))))

; Evaluation count : 6 in 6 samples of 1 calls.
;              Execution time mean : 117.513711 ms
;     Execution time std-deviation : 4.845768 ms
;    Execution time lower quantile : 114.560894 ms ( 2.5%)
;    Execution time upper quantile : 125.913807 ms (97.5%)
;                    Overhead used : 6.488654 ns

; Found 1 outliers in 6 samples (16.6667 %)
; 	low-severe	 1 (16.6667 %)
;  Variance from outliers : 13.8889 % Variance is moderately inflated by outliers

;; ====================

;; Sieve
(defn prime-factors
  [n]
  (let [cache (object-array (repeat (inc n) []))]
    (doseq [i      (range 2 (inc n))
            :when  (empty? (aget cache i)) ; no factors till now => prime!
            j      (iterate #(* i %) i)
            :while (<= j n)
            k      (range j (inc n) j)]
      (aset cache k (conj (aget cache k) i)))
    (map-indexed vector cache)))

(criterium/quick-bench
 (doall
  (prime-factors 100000)))

; Evaluation count : 12 in 6 samples of 2 calls.
;              Execution time mean : 77.708969 ms
;     Execution time std-deviation : 20.836134 ms
;    Execution time lower quantile : 46.265794 ms ( 2.5%)
;    Execution time upper quantile : 96.428094 ms (97.5%)
;                    Overhead used : 6.488654 ns

;; ====================

;; Sieve, loop/recur
(defn prime-factors
  [^long n]
  (let [cache (object-array (inc n))]
    (loop [i 2]
      (when (<= i n)
        (when (empty? (aget cache i))
          (loop [j i]
            (when (<= j n)
              (loop [k j]
                (when (<= k n)
                  (aset cache k (cons i (aget cache k)))
                  (recur (+ j k))))
              (recur (* i j)))))
        (recur (inc i))))
    (map-indexed vector cache)))

(criterium/quick-bench
 (doall
  (prime-factors 100000)))

; Evaluation count : 18 in 6 samples of 3 calls.

;              Execution time mean : 36.971299 ms
;     Execution time std-deviation : 18.298341 ms
;    Execution time lower quantile : 15.875827 ms ( 2.5%)
;    Execution time upper quantile : 54.049373 ms (97.5%)
;                    Overhead used : 6.465751 ns

;; ====================

;; Sieve, mark the smallest factor and collect factors later, loop/recur
(defn prime-factors
  [^long n]
  (let [cache (int-array (range (inc n)))]
    ;; Even numbers
    (loop [i 2]
      (when (<= i n)
        (aset-int cache i 2)
        (recur (+ i 2))))
    ;; Odd numbers
    (loop [i 3]
      (when (<= i n)
        (loop [j (long (+ i i))]
          (when (<= j n)
            (when (= j (aget cache j))
              (aset-int cache j i))
            (recur (+ i j))))
        (recur (+ i 2))))
    (concat [[0 []] [1 []]]
            (map (fn [n]
                   (loop [x  (long n)
                          fx []]
                     (let [y (long (aget cache x))]
                       (if (= x y)
                         [n (conj fx y)]
                         (recur (quot x y) (conj fx y))))))
                 (range 2 (inc n))))))

(criterium/quick-bench
 (doall
  (prime-factors 100000)))

; Evaluation count : 24 in 6 samples of 4 calls.
;              Execution time mean : 43.649073 ms
;     Execution time std-deviation : 15.517053 ms
;    Execution time lower quantile : 26.313619 ms ( 2.5%)
;    Execution time upper quantile : 58.345853 ms (97.5%)
;                    Overhead used : 6.488654 ns

;; ====================

;; Sieve, mark the smallest factor and collect factors later, doseq
(defn prime-factorize-till
  [n]
  (let [smallest-factors (int-array (range (inc n)))
        wheel            (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6  4  2
                                 6 4 6 8 4 2 4 2 4 8 6 4 6 2  4  6
                                 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])
        xf               (comp
                          (take-while #(<= % n))
                          (filter #(= % (aget smallest-factors %))))
        factors-of       (fn factors-of
                           [x]
                           (loop [x  (long x)
                                  fs []]
                             (let [y (aget smallest-factors x)]
                               (if (= x y)
                                 (conj fs y)
                                 (recur (quot x y) (conj fs y))))))]
    (doseq [i (concat
               [2 3 5 7]
               (sequence xf (reductions + 11 wheel)))
            j (range (+ i i) (inc n) i)]
      (when (= j (aget smallest-factors j))
        (aset-int smallest-factors j i)))
    (concat [[] []]
            (map factors-of (range 2 (inc n))))))

(criterium/quick-bench
 (doall
  (prime-factorize-till 100000)))

; Evaluation count : 24 in 6 samples of 4 calls.

;              Execution time mean : 38.933777 ms
;     Execution time std-deviation : 14.025795 ms
;    Execution time lower quantile : 25.300044 ms ( 2.5%)
;    Execution time upper quantile : 60.055388 ms (97.5%)
;                    Overhead used : 6.488654 ns

; Found 1 outliers in 6 samples (16.6667 %)
; 	low-severe	 1 (16.6667 %)
;  Variance from outliers : 81.9398 % Variance is severely inflated by outliers