Haskell 中欧拉空间复杂度的筛选

Question

我得到了两种用 Haskell 编写的不同算法，旨在生成前 k 个素数。顾名思义，它们是 Eratoshenes 和 Euler 的筛子。

我试图理解为什么 Euler 实现使用这么多内存。到目前为止，我认为生成的流数量会迅速爆炸，使内存饱和，但据我所知，它们应该等于 2k - 1，其中 k 是我们想要的素数的索引。所以应该还有其他的大问题。

我尝试通过 GHC 的调试器运行代码，它显示分配的大部分内存来自减函数，所以我认为流肯定是问题的一部分。

这里减去从 tcs 中删除从 p*p 开始的 p 的每一个倍数，它是迄今为止找到的每个素数的互质（p 除外），并最终生成一个新的流传递给下一个递归调用 eulerSieve。

minus :: [Int] -> [Int] -> [Int]
minus xs@(x:txs) ys@(y:tys)
  | x < y = x : minus txs ys
  | otherwise = minus txs tys

eulerSieve :: [Int] -> [Int]
eulerSieve cs@(p:tcs) = p:eulerSieve (minus tcs (map (p*) cs))

在这里阅读我发现空间以 O(k^2) 为界，但它没有准确解释原因。任何建议将不胜感激。