是否有可能懒洋洋地生成轮子？

Question

在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 + p_1...p_n 在其中时 x 在其内部），因此我们称其为轮。

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

因此，当素数的数量趋于无穷大时，Coprime(p_1,...,p_n) 在 1 和 p_n 之间留下了一个巨大的空洞。因此，您能想到的唯一限制是空集：不存在无限轮。