algorithm - clojure 中的链式调用？

Question

我正在尝试在 Clojure 中实现埃拉托色尼筛法。我想测试的一种方法是:

1. 获取范围 (2 3 4 5 6 ... N)
2. 对于 2 <= i <= N
   • 通过 filter 传递我的范围，删除 i
   的倍数
   • 对于i+1次迭代，使用之前过滤的结果

我知道我可以用 loop/recur 做到这一点，但这会导致堆栈溢出错误(由于某些原因未应用尾调用优化)。

我怎样才能迭代地做到这一点？我的意思是对同一个例程调用 N 次调用，将第 i 次迭代的结果传递给 i+1th。

Answer 1

(defn sieve [beg end]
  (letfn [(siever [to-sieve sieved]
                  (if (empty? to-sieve) sieved
                  (let [[f & r] to-sieve]
                    (if (> f (Math/sqrt end)) (into sieved to-sieve)
                        (recur (remove #(zero? (mod % f)) r) 
                           (conj sieved f))))))]
    (siever (range beg (inc end)) [])))

这个似乎工作得很好。用 (sieve 2 1000000) 测试它并在几秒钟内返回而不会吹。