计算最小除数的两个替代函数的性能

Question

在《通往逻辑、数学和编程的 Haskell 之路》一书中，作者提出了两种寻找数字 的最小约数 k 的替代方法n 和 k > 1，声称第二个版本比第一个版本快得多。我无法理解原因(我是初学者)。

这是第一个版本(第 10 页):

ld :: Integer -> Integer -- finds the smallest divisor of n which is > 1
ld n = ldf 2 n

ldf :: Integer -> Integer -> Integer
ldf k n | n `rem` k == 0 = k
        | k ^ 2 > n      = n
        | otherwise      = ldf (k + 1) n

如果我理解正确的话，ld 函数基本上结束了遍历区间 [2..sqrt(n)] 中的所有整数，并在其中之一除 n，将其作为结果返回。

作者声称速度更快的第二个版本是这样的(第 23 页):

ldp :: Integer -> Integer -- finds the smallest divisor of n which is > 1
ldp n = ldpf allPrimes n

ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n | rem n p == 0 = p
              | p ^ 2 > n    = n
              | otherwise    = ldpf ps n

allPrimes :: [Integer]
allPrimes = 2 : filter isPrime [3..]

isPrime :: Integer -> Bool
isPrime n | n < 1     = error "Not a positive integer"
          | n == 1    = False
          | otherwise = ldp n == n

作者声称此版本速度更快，因为它仅遍历 2..sqrt(n) 区间内的 primes 列表，而不是遍历所有素数该范围内的数字。

但是，这个论点并不能说服我:递归函数 ldpf 正在一个接一个地吃掉素数列表 allPrimes 中的数字。此列表是通过对所有整数列表执行filter 生成的。

因此，除非我遗漏了什么，否则第二个版本最终也会遍历 2..sqrt(n) 区间内的所有数字，但对于每个数字，它首先检查它是否为质数(一个相对昂贵的操作)，如果是，它检查它是否划分 n(一个相对便宜的操作)。

我会说只检查 k 是否为每个 k 划分 n 应该更快。我推理的缺陷在哪里？

Answer 1

第二种解决方案的主要优点是您只计算素数列表 allPrimes 一次。由于惰性求值，每次调用只计算它需要的素数，或者重用已经计算过的素数。因此，昂贵的部分只计算一次，然后就可以重复使用。

对于计算单个数字的最小约数，第一个版本确实更有效。但是尝试对 1 到 100000 之间的所有数字运行 ldp 和 ld，您会看到差异。