问题标签 [wheel-factorization]

当按照维基百科上的车轮分解程序进行操作时，我似乎偶然发现了一个问题，如果我尝试构建一个 2-3-5-7 车轮，质数 331 会被视为合数。

带 2-3-5-7 轮，2*3*5*7=210。所以我设置了一个有 210 个插槽的圆圈，并通过步骤 1-7 没有任何问题。然后我到第 8 步，去掉所有素数倍数的辐条，我最终去掉了以 121 为根的辐条，它是 11 的倍数，它是一个素数。对于以 121 为根的辐条，121 + 210 = 331。不幸的是，331 是质数。

维基百科上的程序不正确吗？

还是我误解了程序，应该只删除 2、3、5 和 7 的倍数的辐条，而不是任何其他小于 210 的素数？

我正在实现一个相当快的素数生成器，并通过对 Eratosthenes 的筛子进行了一些优化，获得了一些不错的结果。特别是，在算法的初步部分，我以这种方式跳过了所有 2 和 3 的倍数：

这m_sieve是根据埃拉托色尼筛法的布尔数组。我认为这是一种仅考虑素数 2 和 3 的轮分解，按照模式 2、4、2、4、.. 递增。

我想做的是实现一个更大的轮子，也许考虑素数 2,3 和 5。

我已经阅读了很多关于它的文档，但我没有看到任何使用 Eratosthenes 筛子的实现......示例代码可以提供很多帮助，但也有一些提示会很好:) 谢谢。

我想进一步优化筛子。我已经从http://en.wikipedia.org/wiki/Wheel_factorization#Procedure学习了车轮分解。但我不明白如何在筛子中实现轮分解？

我的老师给了我这个：

n<=10^6;

n 个整数数组：ai..an(ai<=10^9);

找到所有素数。

他说了一些关于 eratosthenes 筛子的事情，我读过它，还有轮分解，但我仍然不知道如何让程序（fpc）在 1 秒内运行。？？据我所知这是不可能的，但仍然想知道你的意见。并且通过车轮分解，一个 2*3 的圆圈会将 25 视为素数，我想问是否有办法找出被错误视为素数的车轮的第一个数字。示例：2*3*5 圆，如何找到第一个被视为质数的合数？请帮忙..对不起英语不好。

我正在从这里修改一个无限期的 Eratosthenes 筛子，因此它使用轮分解来跳过更多的复合材料，而不是目前仅检查所有可能性的形式。

我已经制定了如何生成步骤以到达车轮上的所有间隙。从那里我想我可以用+2代替这些轮步，但这会导致筛子跳过素数。这是代码：

我正在使用它来检查它：

当我将车轮尺寸设置为 0 时，我得到前 100 个素数的正确总和 24133，但当我使用任何其他车轮尺寸时，我最终会丢失素数、不正确的总和和复合。即使是 2-3 轮（使用 2 和 4 的交替步骤）也会使筛子错过质数。我究竟做错了什么？

作为一些Eulerian travails的一部分，我正在尝试使用分解轮编写Eratosthenes 筛。到目前为止，我的代码是：

对于超过 6 个元素的车轮，我得到了以下结果。我真的不明白为什么：

否则，该算法似乎工作正常，并使用具有 6 个或更少元素的轮子生成素数。

显然apply，ring当长长的名单传给他们时，他们会嗤之以鼻。

但是列表不应该算作一个参数吗？我承认我完全糊涂了。任何输入表示赞赏。

我认为这在技术上是车轮分解。我正在尝试重新压缩我的程序对 Eratosthenes 筛的表示，它只包含可能是素数的数字索引。

一些背景：

最基本的轮子是[2]：跟踪2作为第一个素数，筛子只包含奇数索引。(50%))

下一个轮子是[2 3]：跟踪2和3作为第一个素数，筛子只包含2*3=6之间的间隙（即1和5）。索引的形式为 6k+1 和 6k+5。(33%)

下一个轮子是 [2 3 5]：跟踪 2、3 和 5 作为第一个素数，筛子只需要 8 位来表示大小为 30 的区间。（27%）

清除数字倍数的位时，我使用此循环找到这些倍数：

问题在于设置车轮所涉及的时间，以及压缩比的收益递减。好吧，那和 rn 更改为不同的车轮尺寸需要大量的重新计算。此外，通过改变轮子尺寸，我认为我可以影响渐近复杂度。

所以我提出的解决方案是使用小轮子来初始化更大的轮子：[2 3] (6/2) 获得 [2 3 5] (30/8) 轮子中的间隙 [2 3 5] 获得间隙[2 3 5 7] (210/48) 轮

我需要帮助的地方是将已经计算的小筛子映射到要计算的大筛子，这样我就可以避免重新筛选从 1 开始的所有内容。获取前 30 个素数，使用它们找到接下来的 210-30 个素数，用它们来找到接下来的 480-210 个素数。

更具体地说，我需要帮助反转此函数（或正确实现 invIndexOf()）：

此外，自从我计算出任何事物的渐近复杂性以来已经有几年了。我很确定这是一种改进，尽管不是很大。

我在进一步优化我的主要计算功能方面有点挣扎。

到目前为止，我最终得到了 Eratosthenes 的筛子。

我在https://primesieve.org/上找到了通过实施轮子进一步优化这一点的提示以及本文的链接：ftp: //ftp.cs.wisc.edu/pub/techreports/1991/TR1028.pdf

我试图将这个伪代码翻译成 python，但它不能正常工作。我感觉步骤 B 中的迭代不正确。计算时prime_sieve_fast(100, 3)，不删除91 。这是合乎逻辑的，因为运行变量永远不会达到7*13or 13*7。我做错了什么？