haskell - 使用 Haskell 筛选素数

Question

好的，所以我正在尝试编写一个 Haskell 程序，该程序可以非常快地计算素数。想必我不是第一个尝试这样做的人。 (特别是，我该死的确信我看到了一些先前的艺术，但我现在找不到它......)

最初，我想计算小于 10^11 的素数数量。目前我已经让程序运行了大约 15 分钟，但还不到一半。一些狂热的 C++ 程序员声称他的程序只需要 8 秒 分钟。很明显我正在做一些可怕的错误。

(如果重要的话，我当前的实现使用 IOUArray Integer Bool 和多个线程来处理搜索空间的独立子范围。目前从 10MB 中删除所有 2 的倍数需要几秒钟的时间数组 block ...)

请注意，10^11 对于 32 位算术来说太大了。另外，10^11 位 = 12.5 GB，太多的数据无法放入 Haskell 的 32 位地址空间。因此，您无法立即将整个位图存储在内存中。最后，请注意，小于 10^11 的素数数量只是小于 2^32 的一个阴影，因此您也无法一次存储所有实际整数。

<小时/>

编辑:显然我误读了计时信息。 C++ 人员实际上声称的是:

• 仅使用一个核心计算 < 10^11 素数需要 8 分钟，使用 4 个核心需要 56 秒。 (未指定CPU类型。)

• 计算 < 10^10 的素数需要 5 秒。 (不确定使用了多少个核心。)

抱歉，我的错误...

编辑:我的源代码可以在这里找到:http://hpaste.org/72898

Answer 1

使用优秀的StackOverflow老师Daniel Fischer的包arithmoi:

import Math.NumberTheory.Primes.Counting

main = print $ primeCount (10^11)

-- $ time ./arith
-- 4118054813
-- 
-- real 0m0.209s
-- user 0m0.198s
-- sys  0m0.008s

这比你的“狂热”C++ friend 写的东西快 40 倍；也许他可以通过查看 Haskell 源代码学到一两件事......这里有 the haddocks