问题标签 [sieve]

我有一系列随机数。范围实际上由用户确定，但最多为 1000 个整数。它们被放置在这个：

并且值是这样插入的：

我正在创建一个单独的函数来查找所有非质数。这就是我现在所拥有的，但我知道这是完全错误的，因为我在这个系列中得到了素数和复合数。

这种方法通常在我只有从 0 到 1000 的一系列数字时有效，但是当我的数字乱序和重复时，它现在似乎不起作用。有没有更好的方法来查找向量中的非素数？我很想创建另一个向量，用 n 个数字填充它，然后以这种方式找到非素数，但这会效率低下吗？

好的，由于范围是 0-1000，我想知道创建 0-n 排序的向量是否更容易，然后使用筛子找到素数，这是否更接近？

是否有一个函数可以返回第n个素数的近似值？我认为这类似于近似的反素数计数函数。例如，如果我给这个函数 25 它会返回一个大约 100 的数字，或者如果我给这个函数 1000 它会返回一个大约 8000 的数字。我不在乎返回的数字是否是素数，但我确实想要它要快（因此不会生成前n 个素数来返回第n个。）

我想要这样，这样我就可以使用筛子（Eratosthenes或Atkin ）生成前n 个素数。因此，理想情况下， n th的近似值永远不会低估实际n th 素数的值。

（更新：请参阅我的答案，了解找到第n个素数上限的好方法。）

当我偶然发现一种称为欧拉筛的改进版的埃拉托色尼筛时，我正在阅读不同的筛分算法。根据Wikipedia，在 Haskell 中有一个稍微不同版本的想法（称为 Turner's Sieve）的实现。

现在我试图了解给出的代码片段到底是做什么的，我想我已经明白了，但现在我想将代码翻译成 F# 并且真的不知道从哪里开始。我主要担心的是似乎没有“减去”两个序列的功能。

这是代码：

这将如何在 F# 中实现？甚至可能吗？

我认为最好用代码解释，这只是一个简单的例子：

哎呀，太丑了。基本上我有一个集合，我想通过某种筛子将它传递给仅继续处理满足特定条件的对象。我的猜测是有一个比一堆返回布尔值的方法更好的模式。

我在业余时间玩了 Euler 项目，到了需要进行一些重构的地步。我已经实现了 Miller-Rabin，以及一些筛子。我之前听说过筛子实际上对于较小的数字更快，例如在几百万以下。有人有这方面的信息吗？谷歌不是很有帮助。

他们具体是做什么的？我知道 @ 的一种可能用法（在模式匹配开始时分配名称），但在 ~.

我在以下代码片段中找到了它们，取自http://www.haskell.org/haskellwiki/Prime_numbers，但本文假设您精通 Haskell 语法并且不费心解释其深奥的运算符（我的部分'm 困惑的是sieve声明的开始）：

任何关于此处使用的语法的解释（或链接）将不胜感激。

我正在实施 Eratosthenes 筛，对此的解释请参见http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes。但是我想调整它来生成 M 个素数，而不是从 1 到 N 的素数。我这样做的方法是简单地创建一个足够大的 N，以便所有 M 个素数都包含在这个范围内。有没有人有任何好的启发式来模拟素数的增长？如果您希望发布代码片段，我将在 Java 和 C++ 中实现它。

我在解决有关Project Euler的问题时阅读了 Eratosthenes 的筛子。我相信你们知道我在说哪个问题。事情就是这样。我的代码设法正确显示了 100 万以下的所有素数。但是，当我为 200 万个尝试相同的实现时，它给了我一个分段错误...我对错误发生的原因有一定的了解，但不知道如何纠正它...这是 100 万以下素数的代码.

当按照维基百科上的车轮分解程序进行操作时，我似乎偶然发现了一个问题，如果我尝试构建一个 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 的素数？

上面的代码是一个朋友为了得到一个素数而写的。它似乎在使用某种筛分，但我不确定它是如何工作的。下面的代码是我不太棒的版本。我会使用sqrt我的循环，但我看到他在做其他事情（可能与筛分有关），所以我没有打扰。

我的问题是：他到底在做什么？