Clojure 质数惰性序列

Question

以下是 Python 代码，您需要使用 Clojure 实现相同的算法：

from itertools import count
from math import sqrt

def prime_gen():
   primes = []
   for n in count(2):
       if all(n%p for p in primes if p <= sqrt(n)):
           primes.append(n)
           yield n

- Roskoto

---

请注意，Python中确切的算法较弱。请查找Alex Martelli的有效无限质数生成器。 - Hamish Grubijan

https://dev59.com/K3E95IYBdhLWcg3wp_yn - Hamish Grubijan

Answer 1

我尽可能地让它像Python:

(def prime-gen
     (let [primes (atom [])]
       (for [n (iterate inc 2)
             :when (not-any? #(zero? (rem n %))
                             (filter #(<= % (Math/sqrt n)) 
                                     @primes))]
         (do (swap! primes conj n)
             n))))

(take 10 prime-gen)  ; => (2 3 5 7 11 13 17 19 23 29)

Clojure不将整数0视为布尔值假。我花了几分钟才弄清楚你的Python代码正在利用这一点。

这里有一些其他Clojure中的素数算法。此外，clojure.contrib.lazy-seqs中还实现了一个素数实现。

- Brian Carper

---

不需要像 Python 那样 :) 如果有更符合惯用语的 Clojure 解决方案，请也一并发送。 - Roskoto

你应该跟随这个链接。那里有许多示例和答案。还有http://clj-me.cgrand.net/2009/07/30/everybody-loves-the-sieve-of-eratosthenes/#comments。 - dnolen

嗯，除了改变atom之外，它并不是完全不符合Clojure的风格。但要避免使用atom需要进行一些扭曲。有些算法需要副作用和非函数式编程风格（特别是像原地排序、洗牌、特定数学函数等），在这些情况下切换到使用可变数据结构是可以接受的。这就是为什么Clojure提供了它们。你甚至可以深入使用本地Java数据结构来处理这些事情。 - Brian Carper

Answer 2

这个版本比@Brian Carper的要快得多

(def prime-gen
  (let [primes (atom [2N])]
    (iterate
      #(let [ps @primes]
         (loop [n (inc %)]
           (if (loop [i 0]
                 (let [p (nth ps i)]
                   (cond
                     (< n (* p p)) true
                     (zero? (mod n p)) false
                     :else (recur (inc i)))))
             (do (swap! primes conj n) n)
             (recur (inc n)))))
      (first @primes))))

- SaltyEgg

Answer 3

这是一个相当通俗易懂的Clojure算法。我尽量保持名称不变，以便您可以看到此代码的对应关系。

(def all? (partial every? identity))

(defn prime-gen []
  (let [unfold
        (iterate
          (fn step [[primes n]]
            (if (all?
                  (for [p primes :when (<= p (Math/sqrt n))]
                    (not= 0 (mod n p))))
              [(conj primes n) (inc n)]
              (recur [primes (inc n)])))
          [[] 2])]
    (map (comp peek first) (rest unfold))))

每次迭代step

• 将下一个质数附加到其参数的第一个组件中，并
• 将下一个候选质数传递给第二个组件。

最后一行从迭代中挑选出已附加的质数。

它有效：

(take 11 (prime-gen))
=> (2 3 5 7 11 13 17 19 23 29 31)

我们还可以看到一些低效的地方： :when (<= p (Math/sqrt n)子句（以及其Python等价物if p <= sqrt(n)）是无用的。我们仍然会遍历所有发现的primes，而不是在它们变得太大以至于不可能成为因子时停止。为了修复这个问题，

• 在Clojure中，我们将:when替换为:while；
• 在Python中，我认为我们应该使用takewhile来包装primes，而不是在其后跟一个if（未经测试）。

即便如此，该算法仍然很慢。要获得更快的算法，请参见Christophe Grand关于此主题的博客中的lazy-primes3。

- Thumbnail