algorithm - 如何使用埃拉托色尼筛法得到第 n 个素数？

Question

我编写了一个函数，sieve(n)，它使用埃拉托色尼筛法返回一个数组，该数组包含不超过 n 的所有素数。

sieve(25) # ==> [2, 3, 5, 7, 11, 13, 17, 19, 23]

可以阅读此函数的源代码here .

我现在想重构它，以便 sieve(n) 将返回第 n 个素数。我只是不确定我会怎么做。我不想写一个全新的更复杂的函数，所以最好的方法似乎是弄清楚筛子应该算到什么值。

例如，如果我要求第 27 个素数，筛子的初始整数列表应该是 2，直到 (我知道第 27 个素数不大于)。但是有没有一种简单的方法可以计算出该值是多少？

我研究了这个问题并找到了 this Quora post其中表示第 n 个素数必须介于 n*Math.log(n) + n*(Math.log(Math.log(n))-1) 和 n*Math 之间。 log(n) + n*Math.log(Math.log(n))(其中 Math.log 是自然对数的 Ruby)，但只需制作 list 这两个数字之间的数字数组使筛子产生奇怪的值，例如第 15 个素数的 56(56 不是素数，答案应该是 47)。

如您所料，我完全不适合这里。如果有人能给我一些建议，我将不胜感激。

Answer 1

Eratosthenes 的筛法总是要从头开始；您不能在任意间隔内进行筛选，因为您会丢失所有较小的素数。所以你不必关心下限，只关心上限。哪些是你给的，哪些是Wikipedia确认:

p_n <n ln (n ln n) 对于 < i>n ≥ 6

所以简单地接受这个界限，插入你的 n 并迭代直到你找到 n 素数。您的筛子通常会有点太大，但如果边界相当紧的话也不会太大，我希望是这种情况。

参见 here对于该绑定(bind)的表或 here为了情节。顺便说一句，创建表格的代码也在做同样的事情。我想要至少 500 个条目，所以我计算了

n = 500
lst = list(range(2, ceil(n*log(n*log(n)))))
ps = []
while lst:
    p = lst[0] # next prime
    ps.append(p)
    lst = [i for i in lst if i % p != 0]

并从中得到了 500 多个素数，然后我可以向您展示计算出的边界与实际值的比较情况。