1

这是一个 Project Euler 问题。

我从最快的方法中学到了列出 N 以下的所有素数 并实现了一个 clojure ：

(defn get-primes [n]
  (loop [numbers (set (range 2 n))
         primes []]
    (let [item (first numbers)]
      (cond 
        (empty? numbers)
        primes
        :else
        (recur (clojure.set/difference numbers (set (range item n item)))
               (conj primes item))))))

使用如下：

(reduce + (get-primes 2000000))

但是太慢了。。

我想知道为什么，有人可以启发我吗？

4

1 回答 1

3

该算法甚至不正确：在除最后一次之外的每次迭代中，它都会(first numbers)将该点的值添加到primes，但不能保证它实际上是素数，因为使用的集合数据结构是无序的。（Python 原版也是如此，正如其作者在对您链接到的问题的编辑中提到的那样。）因此，您首先需要通过更改(set (range ...))为(into (sorted-set) (range ...)).

即使这样，这也不是一个很好的寻找素数的算法。为了做得更好，您可能希望使用 Java 数组和/编写Eratosthenes 筛的命令式实现，或者可能是功能性的类似 SoE 的算法，例如 Melissa E. O'Neill 的精美论文The Genuine Sieve of Eratosthenes .looprecur

于 2013-06-15T05:43:10.710 回答