找到前n个素数？

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 ln(n) + n ln( ln(n) )

对于 n >= 6

因此，如果您使用下一个大于上述右侧的整数运行当前函数（或者，例如，其他答案中提到的筛子之一），您一定会找到第 n 个素数。