问题标签 [sieve]

我需要找到第 N 个素数的反向操作，即给定一个素数，我需要找到它在

素数可以很大，大约为10^7. 此外，还有很多。

我有一个预先计算的素数索引，可以进行二进制搜索，但我也有 50k 的空间限制！可以过筛吗？或者还有什么快速的方法？

编辑：非常感谢所有精彩的答案，我没想到他们！我希望它们对寻求相同的其他人有用。

我正在尝试输出前 100 个素数并不断收到错误消息：

申请：不是程序；期望一个可以应用于给定参数的过程：(#) arguments...: [none]

错误显示在我的 take$ 过程中：

这是我所有的代码：

感谢您的任何帮助，您可以提供。

这个程序是一个 c++ 程序，它使用 Eratosthenes 的筛子来计算素数来找到素数。然后应该存储执行此操作所需的时间，并重新执行计算 100 次，每次存储时间。在这个程序中有两件事我需要帮助：

首先，我只能测试高达 4.8 亿的数字，我希望得到更高的数字。

其次，当我给程序计时时，它只会得到第一个计时，然后打印零作为时间。这是不正确的，我不知道时钟有什么问题。-谢谢您的帮助

这是我的代码。

I am stuck on trying to get the sieve to work. When I debug it, it tells me that stuff like 9 and 15 still evaluate to true when they go through the sieve. What causes this? Also, am I using the vector properly to get the highest prime factor?

好的，所以我创建的这个函数使用 Eratosthenes 算法来计算所有素数 <= n。该函数在参数中存储素数和素数。

当函数退出时，素数应该指向一块动态分配的内存，其中包含所有素数<= num。 *count将有素数的计数。

这是我的功能getPrimes：

现在，这是预期的输出和我的输出。如您所见，我的getPrimes功能中有问题，但我不确定是什么。

到目前为止，人们向我指出了以下 3 个问题：

1. 错误的删除过程if (sieve[multiple]) {数组筛子索引有偏差
2. (*array) = sieve;泄漏刚刚分配的内存，并让我们*array指向一个在函数返回时不再存在的局部变量——你会得到一个悬空指针。
3. if(sieve[i] != NULL)应该使用 0，而不是 NULL，你没有指针数组。

但是，我不太确定如何解决已为我发现的悬空指针/内存问题。除此之外，我想知道我的代码中是否还有其他错误，因为我不太清楚为什么我的输出中的数字添加了 0...不要担心不同的输出样式，只是额外的数字. 谢谢你能帮我解决这个问题！

好的，所以我创建的这个函数使用 Eratosthenes 算法来计算所有素数 <= n。该函数在参数中存储素数和素数。

当函数退出时，素数应该指向一块动态分配的内存，其中包含所有素数<= num。*count 将有素数的计数。

这是我的函数 getPrimes：

我的函数在这里编译得很好，但是我注意到当我尝试从 101 开始的更大数字时出现分段错误。有谁看到我的代码在哪里产生分段错误？

下面是两个可以完美编译的函数，但我似乎在第一个输入的整数时遇到了一个奇怪的错误。我已经尝试在 GDB 中进行调试，但是当只有第一个输入值出现这个奇怪的错误时，它会让事情变得复杂。

我们的输出：

预期的输出显然应该只显示 2。对于第一个输入的整数，从 2 到 2000 的任何整数都是这种情况。最后一个或最后 2 个素数打印非常大的数字，有时甚至是负数。我不知道为什么，但是在第一个输入值之后一切正常。疯狂地尝试用 GDB 调试它，但没有运气。非常感谢有人对这个奇怪的错误的帮助

我正在尝试学习 python，我认为尝试开发自己的初筛将是下午的一个有趣问题。到目前为止，当需要时，我只需导入我在网上找到的埃拉托色尼筛网的一个版本——我用它作为我的基准。

在尝试了几种不同的优化之后，我认为我已经写了一个相当不错的筛子：

使用前 1,000,000 个整数作为我的范围，此代码将生成正确数量的素数，并且仅比我的基准测试慢 3-5 倍。当我在更大的范围内尝试它时，我正要放弃并拍拍自己的背，但它不再起作用了！

我认为问题来自与[****]，但我无法弄清楚为什么它如此破碎。它应该将“j”的每个奇数倍数标记为 False，并且它在大多数情况下都有效，但是对于 4,194,304 以上的任何东西，筛子都被打破了。（公平地说，它也会随机破坏其他数字，例如 10,000）。

我进行了更改，它显着减慢了我的代码速度，但它实际上适用于所有值。这个版本包括所有数字（不仅仅是赔率），但其他方面是相同的。

谁能帮我弄清楚为什么我的原始功能（sieve3）不能始终如一地工作？

编辑：我忘了提，当 Sieve3“中断”时，sieve3(n) 返回 n/2。

我正在尝试为我作为练习编写的 RSA 实现实现素数测试。我主要使用 Rabin-Miller，但我确实有一个埃拉托色尼筛法，制定了一个低于 1000 个素数的列表，用于快速测试以确定候选人是否将其中一个作为素数。

相关功能是：

其中 primeList 是 Sieve 生成​​的素数列表。这在 to_test 值为 2^55 左右的情况下非常有效，但超过了这一点

语句总是计算为 0.0，即使当我将它交给拉宾米勒确定为素数的 to_test 时也是如此。我不确定这可能是什么。我不太清楚 Python 如何处理非常大的数字，但据我所知 2^55 似乎不会是任何类型的溢出边界。使用 Sieve 时，该功能明显更快，并且为 2048 位实现生成密钥需要一段时间，所以即使这是一个练习，我想看看我是否可以让 Sieve 工作。

提前致谢。

为所有数字 1-n 创建一个除数计数筛是众所周知的

但是，如果我不是为形式 1 * n 的数字创建筛子，而是希望为形式为 6n^2 的数字创建除数，该怎么办？

因此，与其查找 1、2、3、4、5 等的除数，不如查找 6、24、54、96、150 等的除数

但实际上只是形式 kn^p 的数字，以一种有效的方式，所以我实际上并没有存储一个大小为 kn^p 的最大数组。好像我应该只需要大小为 N 的数组，只有每个点代表 kn^p 的除数