问题标签 [sieve]

我知道可以实施 Eratosthenes 筛，以便它在没有上限的情况下连续找到素数（分段筛）。

我的问题是，阿特金/伯恩斯坦的筛子能否以同样的方式实施？

相关问题：C#：如何使阿特金筛子增量

然而，相关问题只有 1 个答案，上面写着“所有筛子都不可能”，这显然是不正确的。

在自然数系列中，我们必须在第一遍中删除每个第二个元素。然后在剩余的元素中，删除第二遍中的每个第 3 个元素。然后在第 K 次通过时，从剩余元素中删除每个第 (k+1) 个元素。

这个系列会这样

第一次通过后（删除每个第二个元素后），

在第二遍之后，（在删除每个第三个元素之后），

第 3 遍后，（每删除第 4 个元素后），

所以，在无限通过之后，它会变成

该系列也称为 Flavius-Josephus 筛。

解决方案是找到系列中的第 6 个元素：

• 做 6^2 = 36
• 下降到 5 的倍数，得到 35
• 然后下降到 4 = 32 的倍数
• 然后下降到 3 = 30 的倍数
• 然后下降到 2 = 28 的倍数
• 然后下降到 1 = 27 的倍数
• 所以第六个幸运数字是27。

虽然它有效，但我不明白解决方案是如何工作的？

交流计划是，

解释此http://oeis.org/A000960的链接

我需要将循环中的整数与 along和 a的商进行比较long。为了不进行整数除法，如果我理解正确，是否需要将其中一个长整数转换为双精度整数？

那是代码片段。primes是一个用 s 填充的数组long。顺便说一句，这段代码是否正确：

因为我担心 along * int不适用于数组索引。

非常感谢！

我尝试为此[问题]实现分段筛算法：http://www.spoj.pl/problems/PRIME1/，如下所示：

尽管如此，我还是得到了 TLE .. 我不明白还需要什么其他优化。请帮助..

编辑1：只是试图在恒定时间内实现 fd_p() ... [失败] .. plz 如果你能帮助我解决这个错误..

编辑 2：问题已解决。

在过去的 5 个小时里，我倾注了我的代码，但一无所获。每当我运行我的代码时，我都会遇到分段错误。有时它发生在客户端，有时发生在服务器端，所以我只是不确定发生了什么。 当我尝试查找最大为 100 的素数时，该代码有效，但之后就没有了。当我上次在这里发布时，我被告知要发布我的完整代码，所以这里是：

服务器：

客户：

我正在用 Python 进行 Eratosthenes 的筛分实现。出现的问题不是所有素数都出现（主要是编号较低的素数）。

这是我的代码：

如果我输入>>> prevPrimes(1000)，我希望结果以：[2, 3, 5, 7, 11, 13, 17]等开头。但是，这就是它的样子：[1, 37, 41, 43, 47, #more numbers]。

我知道问题在于它陈述了“原始”素数（2、3、5、7、11、13、17 等），False因为我的程序检查素数的方式。我怎样才能避免这种情况？提前致谢 ：）

我的输入是一个Integer. 在该值之前，应该找到所有质数并将其打印在 5 列中，然后我必须对整数进行“质数分解”并打印结果。

挺好用的，就是太慢了。。。

}

我在哪里可以节省一些资源？顺便说一句，我现在只能使用数组......对不起德国人的评论。只是如果一些真正不必要的长循环或类似的东西引起了你的注意

谢谢！

我根据维基百科页面上指定的基本算法在 Haskell 中实现了二次筛。它适用于大多数整数，但是它无法找到n次幂的数字 N 的因式分解。对于偶数幂（平方），算法循环，对于奇数幂，我找到了几个平方模 N 的平滑数（我已经测试并证实了这一点），但是每一个派生的平方同余（也经过测试和证实）只会导致一个微不足道的因素。

我有理由确定我已经实现了 Wikipedia 算法。那个版本的算法是否存在问题，阻止它处理n次幂，或者我的算法中是否存在错误？

出于某种原因，stackoverflow 在格式化我的代码时遇到问题，所以你去： http: //pastebin.com/miUxHKCh

欧拉筛比埃拉托色尼筛具有更好的渐近复杂度，并且可以用命令式语言简单地实现。

我想知道是否有任何方法可以用流优雅地实现它。我已经检查了haskell wiki 关于素数的信息，但是这两种实现比该 wiki 中的其他筛子（甚至是试除法！）慢数百倍。

所以我尝试自己写：

minus类似于minusin Data.List.Ord。

takeWhile'与 类似takeWhile，但有细微差别：takeWhile删除不满足谓词的第一个元素；takeWhile'会接受的。

lsp i返回 i 的有限乘积流，素数不超过 i 的最小素数。

可悲的是，我的实现运行速度非常慢......而且我找不到罪魁祸首。

无论如何，是否有可能以流处理方式实现高效的欧拉筛？还是该算法具有与流的本质相反的固有特性？

我想知道是否有办法将现有列表分割成某个最有可能不在列表中的数字。例如，假设我有：

现在我想测试数字 11 的整洁度。我将通过在 1 + 整数平方根 11 的限制下尝试除以所有素数来做到这一点。因此，一旦元素大于限制，我不会循环遍历列表的所有元素，素数并打破循环，我想知道我是否可以将列表拼接到 Limit 的值。在这种情况下，该值为：

所以我可以遍历primes[ : up until the value of 4]or的元素[2,3]

我知道一些python，但我不确定如何仅使用列表方法来做到这一点......对于高达数十亿的筛选方法，我可以通过不使用if语句来有效地节省时间......

再次提前感谢！