clojure - Clojure 中的快速素数生成

Question

我一直在努力解决 Project Euler Clojure 中的问题变得更好，而且我已经遇到过几次素数生成。我的问题是它花费的时间太长了。我希望有人能帮助我找到一种有效的方法，以 Clojure 风格的方式来完成这项工作。

当我用拳头做这件事时，我是用暴力破解的。这很容易做到。但是在 Xeon 2.33GHz 上以这种方式计算 10001 个质数需要 2 分钟，对于规则来说太长了，而且通常来说太长了。这是算法:

(defn next-prime-slow
    "Find the next prime number, checking against our already existing list"
    ([sofar guess]
        (if (not-any? #(zero? (mod guess %)) sofar)
            guess                         ; Then we have a prime
            (recur sofar (+ guess 2)))))  ; Try again                               

(defn find-primes-slow
    "Finds prime numbers, slowly"
    ([]
        (find-primes-slow 10001 [2 3]))   ; How many we need, initial prime seeds
    ([needed sofar]
        (if (<= needed (count sofar))
            sofar                         ; Found enough, we're done
            (recur needed (concat sofar [(next-prime-slow sofar (last sofar))])))))

通过将 next-prime-slow 替换为考虑了一些额外规则(例如 6n +/- 1 属性)的较新例程，我能够将速度提高到大约 70 秒。

接下来，我尝试在纯 Clojure 中制作埃拉托色尼筛。我认为我没有解决所有错误，但我放弃了，因为它太慢了(我认为甚至比上面的更糟糕)。

(defn clean-sieve
    "Clean the sieve of what we know isn't prime based"
    [seeds-left sieve]
    (if (zero? (count seeds-left))
        sieve              ; Nothing left to filter the list against
        (recur
            (rest seeds-left)    ; The numbers we haven't checked against
            (filter #(> (mod % (first seeds-left)) 0) sieve)))) ; Filter out multiples

(defn self-clean-sieve  ; This seems to be REALLY slow
    "Remove the stuff in the sieve that isn't prime based on it's self"
    ([sieve]
        (self-clean-sieve (rest sieve) (take 1 sieve)))
    ([sieve clean]
        (if (zero? (count sieve))
            clean
            (let [cleaned (filter #(> (mod % (last clean)) 0) sieve)]
                (recur (rest cleaned) (into clean [(first cleaned)]))))))

(defn find-primes
    "Finds prime numbers, hopefully faster"
    ([]
        (find-primes 10001 [2]))
    ([needed seeds]
        (if (>= (count seeds) needed)
            seeds        ; We have enough
            (recur       ; Recalculate
                needed
                (into
                    seeds    ; Stuff we've already found
                    (let [start (last seeds)
                            end-range (+ start 150000)]   ; NOTE HERE
                        (reverse                                                
                            (self-clean-sieve
                            (clean-sieve seeds (range (inc start) end-range))))))))))

这很糟糕。如果数字 150000 较小，也会导致堆栈溢出。尽管事实上我正在使用 recur。那可能是我的错。

接下来我尝试了一个筛子，在 Java ArrayList 上使用 Java 方法。这需要相当多的时间和内存。

我最近的尝试是使用 Clojure 散列图进行筛选，将所有数字插入筛选中，然后分离非素数。最后，它获取 key 列表，即它找到的素数。找到 10000 个质数大约需要 10-12 秒。我不确定它是否已完全调试。它也是递归的(使用递归和循环)，因为我正在尝试成为 Lispy。

对于这类问题，问题 10(求和 2000000 以下的所有素数)让我很难受。我最快的代码给出了正确的答案，但它花了 105 秒才完成，并且需要相当多的内存(我给它 512 MB 只是为了让我不必大惊小怪)。我的其他算法需要很长时间，我总是先停止它们。

我可以使用筛子在 Java 或 C 中非常快速地计算出那么多素数，而无需使用太多内存。我知道我一定是在我的 Clojure/Lisp 风格中遗漏了导致问题的某些东西。

我真的做错了什么吗？ Clojure 处理大序列是否有点慢？阅读 Euler 项目的一些讨论，人们已经在 100 毫秒内计算出其他 Lisp 中的前 10000 个素数。我意识到 JVM 可能会减慢速度，而 Clojure 相对较新，但我预计不会有 100 倍的差异。

谁能告诉我在 Clojure 中快速计算素数的方法？

Answer 1

这是庆祝 Clojure 的 Java 互操作 的另一种方法。这在 2.4 Ghz Core 2 Duo(运行单线程)上需要 374 毫秒。我让 Java 的 BigInteger#isProbablePrime 中高效的 Miller-Rabin 实现处理素数检查。

(def certainty 5)

(defn prime? [n]
      (.isProbablePrime (BigInteger/valueOf n) certainty))

(concat [2] (take 10001 
   (filter prime? 
      (take-nth 2 
         (range 1 Integer/MAX_VALUE)))))

Miller-Rabin 5 的确定性对于比这大得多的数字可能不是很好。该确定性等于 96.875% 确定它是素数 (1 - .5^certainty)