我一直致力于解决Clojure 中的Project Euler问题以变得更好，并且我已经遇到过几次素数生成问题。我的问题是它需要的时间太长了。我希望有人可以帮助我找到一种有效的方法来以 Clojure-y 方式执行此操作。
当我用拳头做这件事时，我是蛮力的。这很容易做到。但是在 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 中制作一个 Eratosthenes 筛子。我不认为我把所有的错误都解决了，但我放弃了，因为它太慢了（我认为甚至比上面的还要糟糕）。
(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 哈希映射的筛子，将所有数字插入筛子中，然后分解非素数的数字。最后，它获取密钥列表，这是它找到的素数。找到 10000 个素数大约需要 10-12 秒。我不确定它是否已完全调试。它也是递归的（使用递归和循环），因为我想成为 Lispy。
因此，对于这些问题，问题 10（总结 2000000 以下的所有素数）正在杀死我。我最快的代码给出了正确的答案，但它花了 105 秒，并且需要相当多的内存（我给它 512 MB 只是为了不用大惊小怪）。我的其他算法花了很长时间，我总是先停止它们。
我可以使用筛子快速计算 Java 或 C 中的许多素数，而无需使用太多内存。我知道我的 Clojure/Lisp 风格中一定遗漏了一些导致问题的东西。
我做错了什么吗？Clojure 在处理大序列时会有点慢吗？阅读一些 Euler 项目的讨论，人们在 100 毫秒内计算了其他 Lisps 中的前 10000 个素数。我意识到 JVM 可能会减慢速度，而且 Clojure 相对年轻，但我不希望有 100 倍的差异。
有人可以告诉我在 Clojure 中计算素数的快速方法吗？