找到第一个素数？

Question

可能重复： 在python中列出N以下所有素数的最快方法

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

Answer 1

从估计g(n) = n log n + n log log n*开始，它估计n> 5的n个素数的大小。

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

然后考虑一下"在python中列出N以下所有素数的最快方法“中的答案。

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

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

Answer 2

根据这，第n个素数p_n满足

p_n

N >= 6

因此，如果您使用大于右方的下一个整数来运行当前函数(例如，其他答案中提到的一个筛子)，则可以确保找到第n个素数。

Answer 3

你想要埃拉托斯提尼筛。

使用π函数估计n的值，稍微超调，然后使用一个筛子计算到需要的点。