我怎样才能使用Eratosthenes的Sieve获得第n个素数？

Question

我编写了一个函数,sieve(n)它使用了Eratosthenes的Sieve来返回所有素数的数组n.

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

可在此处阅读此功能的来源.

我现在要重构这个,以便sieve(n)返回nth prime.我只是不确定我是怎么做到的.我不想写一个全新的更精细的功能,所以看起来最好的方法是弄清楚筛子应该达到什么价值.

例如,如果我要求第27个素数,那么筛子的初始整数列表应该是2 (我知道第27个素数不大于).但有没有一种简单的方法来确定这个价值是什么？

我研究这个问题,并发现这Quora的帖子里面说,第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这两个数字之间的数字阵列使得筛产量怪异的值,比如56为第15个素数(56不是素数,答案应该是47).

你可以猜到,我完全脱离了我的元素.如果有人能给我一些建议,我真的很感激.

Answer 1

埃拉托色尼的筛子总是要从头开始；你不能在任意区间内进行筛选，因为你会失去所有较小的素数。因此，您不必关心下限，只需关心上限。您给出的内容以及维基百科确认的内容：

\n\n

p _n < n ln ( n ln n ) 对于n \xe2\x89\xa5 6

\n\n

因此，只需取该界限，代入n并迭代，直到找到n 个素数。你的筛子通常会有点太大，但如果边界相当紧的话也不会太大，我希望是这种情况。

\n\n

请参阅此处查看该范围的表格或此处查看绘图。顺便说一下，创建表的代码正在做同样的事情。我想要至少 500 个条目，所以我计算了

\n\n

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

\n\n

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

\n