寻找前n个质数？

Question

可能是重复：
Python中列出小于N的所有素数的最快方法

虽然我已经编写了一个函数来查找n以下的所有质数（primes(10) -> [2, 3, 5, 7]），但我很难找到一种快速找到前n个质数的方法。这样做的最快方式是什么？

- John Howard

---

不是重复：原帖想要前 n 个质数，而不是小于 n 的所有质数。 - Cameron Skinner

重复的问题：https://dev59.com/k3E85IYBdhLWcg3wMQhm - Russell Dias

“找到前n个质数”和“找到小于n的所有质数”几乎没有区别。任何能够找到小于k的所有质数的算法都可以轻松地修改，以继续增加k，直到找到n个质数为止。 - Olhovsky

@Cameron Skinner，说得好。 我已经添加了一个答案来解决这些问题。 - Olhovsky

这不是重复的问题，它与提出的重复问题有所不同。首先n个质数与所有小于n的质数。 - Olhovsky

Answer 1

从估计值g(n) = n log n + n log log n*开始，该估计值估计了n大于5时第n个素数的大小。

然后在该估计值上运行筛法。g(n)给出了一个过高的估计值，这没关系，因为我们可以简单地丢弃生成的额外的大于所需n的素数。

然后考虑以下内容：“Fastest way to list all primes below N in python”中的答案。

如果您关心代码的实际运行时间（而不是算法的时间复杂度的数量级），请考虑使用其中一种使用numpy的解决方案（而不是其中一种“纯Python”解决方案）。

*当我写log时，我指的是自然对数。

- Olhovsky

---

我不确定该怎么办...我的代码 primes(int(pi*n))[:n] 只能返回小于12的正确质数个数。 - John Howard

你的代码应该运行 primes(g(n))。我不确定那是否是你的意思。在我的答案中，g(n) 函数出现了错误，请使用新函数再试一次。 - Olhovsky

Answer 2

根据这里的内容，第n个质数p_n满足以下不等式：

p_n < n ln(n) + n ln( ln(n) )

对于n >= 6

因此，如果您使用上述不等式右侧的下一个整数运行当前函数（或其他筛法），则可以保证找到第n个质数。

- David Norman

Answer 3

你需要埃拉托斯特尼筛法。

使用π函数来估计你想要查找的n值，稍微超过一点，然后使用筛法计算到你需要的点。

- Phrogz

---

+1 如果你把名称翻译正确，-1 如果你提出了相同（不正确）的解决方案。 - Chris Lutz

@ChrisLutz 我想我应该为在编辑之前就回答而受到惩罚，但在我的编辑后，对我来说使用π来估计合理的超调并在到达目标之前停止似乎是合理的。我将不得不看看重复的答案建议了什么。 :) - Phrogz

我在这个问题中没有进行任何负分投票。我的回答是幽默的，因为我的计算结果为零。 - Chris Lutz

@ChrisLutz 我明白，我过去也曾经发表过很多类似的“无投票”评论。 :) - Phrogz

Answer 4

我不知道它是否最快，但欧拉筛法看起来不错。

编辑

正如其他答案所建议的，您可以使用素数定理的基本事实。或者您可以学习基础代数几何并使用椭圆曲线素性测试。

- Vicfred

---

这是另一种在n以下找质数的方法。 - Chris Lutz

我已经找到了大约172个小于n的素数函数，我正在寻找一个前n个素数的代码。 - John Howard

Answer 5

使用埃拉托色尼筛法，利用质数在2和3之后要么是6n+1的形式，要么是6n-1的形式。这将提高程序的速度。

- catchmrbharath