Haskell 素性测试优化。埃拉托斯特尼筛法比直接求解运行得慢

Question

使用此代码来识别素数：

sieve:: [Integer] -> [Integer]
sieve [] = []
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

isPrime' :: Integer -> Bool
isPrime' 2 = True
isPrime' x = x == last (sieve [2..x])

isPrime :: Integer -> Bool
isPrime 2 = True
isPrime p = p > 2 && (all (\n -> p `mod` n /= 0) $ takeWhile (\n -> n * n <= p) [3, 5 ..])

函数

isPrime'

比

isPrime

运行慢得多并且占用更多空间。使用

elem

代替

last

也会运行缓慢。

ghci> isPrime' 10007
True
(0.33 secs, 181,461,088 bytes)
ghci> isPrime 10007
True
(0.01 secs, 92,120 bytes)

怎样才能让

isPrime'

跑得更快？我认为这可能是惰性评估，但我不知道如何解决它。

Answer 1

首先，

isPrime

函数有一个小错误，确实，对于

all

大于True的偶数，它会返回

2

，例如：

ghci> isPrime 4
True

但是我们可以用以下方法解决这个问题：

isPrime :: Integer -> Bool
isPrime p = p == 2 || (odd p && (all (\n -> p `mod` n /= 0) $ takeWhile (\n -> n * n <= p) [3, 5 ..]))

isPrime'

速度慢并不奇怪：它需要构造并列出最多该数量的素数，其运行时间为 O(n×p)，其中 n 是要检查的数字，p 是要检查的数字。达到该数的素数个数。事实上，我们首先有一个直到该数字的所有整数的列表，然后我们过滤掉所有可被二整除的项目，然后我们再次枚举以检查过滤出可被三整除的项目，然后我们枚举剩余的列表以过滤掉项目可被五整除，依此类推。尽管要过滤的列表总是较小，但它仍然会建立很多模检查：例如，将检查元素

11

是否为模

2

、

3

、

5

和

7

。因此它执行了大量工作来获取下一个元素。即使我们想知道 17 是否是素数，我们也需要进行这些检查。而

isPrime

函数不必首先验证 11 是否为素数，而是检查 17 是否为素数。

另一方面，

isPrime

在

O(√n)中运行，其中n是要检查的数字，所有这些检查都是在同一个数字上执行的：我们要检查的数字。所以这是一种更直接的方法来检查某物是否是质数。

我认为这可能是惰性评估，但我不知道如何解决它。

不，惰性求值最多只会产生很小的影响，惰性函数的记账确实有一些开销，但通常不会那么多。

筛法可以改进，因为如果

p是素数，就足以滤除p2，p2^+p，p2^+2p，p 2^+3p等，因此这可以显着减少模检查。但仍然可能会执行很多额外的工作。毕竟，筛法主要用于生成所有素数列表（直到某个上限），而不是检查单个元素是否是素数。