4

我正在通过项目 euler 学习 clojure，并且正在研究第 10 号问题（找到低于 200 万的所有素数的总和。我为 Eratosthenes 的筛子实现了一个非常字面的算法，但它的工作速度太慢而无法使用高达 200 万。我尝试使用 loop-recur 来实现它，以不创建任何新帧，但这对性能没有太大影响。

(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))
4

2 回答 2

2 
(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

于 2011-06-18T15:04:15.377 回答
1

就个人而言，我会以不同的方式构造代码。我有这个问题的实现，它首先生成所有素数的惰性序列，然后对前 2,000,000 个项目求和。在 clojure 1.2 上需要 16 秒，但除了使用 recur 之外几乎没有优化。

与输入范围相比，您还做了很多不必要的事情；(remove #(zero? (mod % (first n))) n)针对所有奇数测试所有候选人，这是无稽之谈**，尤其是当你用 doall 强制它时。实际上，您只需x针对所有已知的素数 <= sqrt(x) 测试候选素数，并在找到第一个匹配项时丢弃该候选人。

** 我刚刚注意到你的算法并不那么愚蠢，但我仍然建议你重写你的算法，因为惰性序列会在给定先前素数和候选数的情况下找到“下一个素数”。

于 2011-06-17T13:26:21.050 回答