寻找前n个质数？

Question

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

虽然我已经写了一个函数来找出小于n的所有质数（primes(10) -> [2, 3, 5, 7]），但我在寻找一个快速的方法来找到前n个质数时遇到了困难。有没有什么最快的方法可以做到这一点？

Answer 1

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

可以使用π这个函数来估算一下你想要查找的数字范围，稍微多估算一点，然后再用筛法计算到你需要的那个点。

Answer 2

根据这个链接，第n个质数p_n满足以下条件：

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

这个公式适用于n大于等于6的情况。

所以，如果你用比上面公式右边的结果大一点的整数来运行你现在的函数（或者其他答案中提到的筛法），你就一定能找到第n个质数。

Answer 3

首先，我们从一个估算开始，g(n) = n log n + n log log n，这个公式可以用来估算第n个质数的大小，适用于n大于5的情况。

接下来，我们可以在这个估算值上运行一个筛选算法。g(n)会给出一个偏大的估算，这没关系，因为我们可以简单地丢掉那些比我们想要的n大的多余质数。

然后，可以参考一下在“Python中列出所有小于N的质数的最快方法”中提到的答案。

如果你关心代码的实际运行时间（而不是算法的时间复杂度），可以考虑使用一些基于numpy的解决方案，而不是那些“纯Python”的方案。

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