找到第 n 个素数的更好算法？

Question

到目前为止，我一直在使用埃拉托色尼筛法生成所有 'n' 个素数。

但是，我想知道是否存在更好的算法，或者我们可以改进现有的性能更好的算法吗？？

Answer 1

对于足够大的N（例如超过一百万左右），最好的算法是使用近似值（例如对数积分或黎曼R函数），然后使用快速素数计数方法例如LMO，然后筛选小的余数。这比筛分快很多数量级。

见https://math.stackexchange.com/questions/507178/most-efficient-algorithm-for-nth-prime-deterministic-and-probabilistic

至少有两个开源实现。

• https://metacpan.org/pod/ntheory
• https://github.com/kimwalisch/primecount

后者超越了第一个，也是多线程的。

添加：Will Ness 还指出了来自 Daniel Fischer 的一个很好的 post，它提供了解决这个问题的不同方法的演练：Calculating and printing the nth prime number