clojure - 如何提高我的 clojure eratosthenes 算法的性能？

Question

我正在通过项目 euler 学习 clojure，并且正在处理第 10 号问题(找到所有小于 200 万的素数的总和。我为埃拉托色尼筛实现了一个非常简单的算法，但它运行得太慢了对多达 200 万有用。我尝试使用循环递归实现它以不创建任何新帧，但这对性能没有太大影响。

(defn find-primes-sum [last-prime nums]
    (loop [p last-prime n nums sum 0]
        (println p)
        (if (empty? n)
        sum
            (recur (first n) (doall (remove #(zero? (mod % (first n))) n)) (+ sum (first n))))))

(defn sieve-primes-until [limit]
    (find-primes-sum 2 (filter odd? (range 2 (inc limit)))))

(println (sieve-primes-until 2000000))

Answer 1

(set! *unchecked-math* true)

(defmacro iloop [[b t n] & body]
  `(loop [~@b]
     (when ~t
       ~@body
       (recur ~n))))

(defn count-primes [^long n]
  (let [c (inc n)
        ^booleans prime? (make-array Boolean/TYPE c)]
    (iloop [(i 2) (<= i n) (inc i)]
      (aset prime? i true))
    (iloop [(i 2) (<= (* i i) n) (inc i)]
      (if (aget prime? i)
        (iloop [(j i) (<= (* i j) n) (inc j)]
          (aset prime? (* i j) false))))
    (areduce prime? i r 0
      (if (aget prime? i)
        (inc r)
        r))))

此版本针对 Clojure 1.3.0 alpha。在我的机器上，它在 2 秒内最多可以计算出 1e8 个素数。它可以很容易地改变以收集它们。它最初是为了表明您可以实现筛子，使其运行速度与可比较的 Java 一样快。

http://dosync.posterous.com/lispers-know-the-value-of-everything-and-the