<分区>
Possible Duplicate:
Fastest way to list all primes below N in python
尽管我已经编写了一个函数来查找 n 下的所有素数 (primes(10) -> [2, 3, 5, 7])，但我正在努力寻找一种快速的方法来找到前 n 个素数。最快的方法是什么？
<分区>
Possible Duplicate:
Fastest way to list all primes below N in python
尽管我已经编写了一个函数来查找 n 下的所有素数 (primes(10) -> [2, 3, 5, 7])，但我正在努力寻找一种快速的方法来找到前 n 个素数。最快的方法是什么？
最佳答案
从估计 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时，我指的是自然对数。
关于python - 找到前 n 个素数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4911777/