algorithm - 是否可以懒惰地生成轮子？

Question

关于 The Genuine Sieve of Erastosthenes在论文中，作者使用有限尺寸的轮子来跳过检查筛结构上前 N 个素数的倍数。例如，为了避免检查 2, 3 的倍数，您可以从 5 开始，交替添加 2 和 4。这就是 wheel 2 如下:

-- wheel 0 = ([2],[1])
-- wheel 1 = ([3,2],[2])
-- wheel 2 = ([5,3,2],[2,4]) -- "start at 5, add 2, 4, 2, 4..."
-- wheel 3 = ([7,5,3,2],[4,2,4,2,4,6,2,6])

她的轮子在筛分过程开始时完全生成。这是一个权衡，因为更大的轮子需要更多的内存。不过，我发现轮子生成背后的底层机制本身很有趣。鉴于其明显的重复性，我想知道是否有可能创建一个“无限轮”，它像筛子一样，呈现为流？我猜，这个流是列表序列 [1], [2], [2, 4], [4, 2, 4, 2, 4, 6, 2, 6] 的限制。 .. - 并且可能作为 primes 本身的实现。

Answer 1

正如 Bakuriu 所说，车轮顺序没有限制。没有“无限轮”这样的东西，我将尝试证明原因。

如果我们知道第一个质数 p_1,...,p_n，我们只需要在与它们互质的数中搜索下一个:

isCoprime :: [Int] -> Int -> Bool
isCoprime ps x = all (\p -> x `mod` p /= 0) ps 

集合 Coprime(p_1,...,p_n) 是 (p_1...p_n)-周期性的(x 在其中当且仅当 x + p_1...p_n 在其中)，所以我们称它为一个轮子。

随着我们采用越来越多的质数 p_i，您要求这个互质数集的极限。然而，在 Coprime(p_1,...,p_n) 中，p_n 下方的唯一数字是 1。为了证明这一点，观察这样一个数字的质因数将是 p_i 之一。

因此随着素数的数量趋于无穷大，Coprime(p_1,...,p_n) 在 1 和 p_n 之间留下了一个巨大的空洞。因此，您能想到的唯一限制是空集:没有无限的轮子。