我已经编写了一个名为sieve(n)
的函数,它使用埃拉托斯特尼筛法返回一个包含所有小于n
的质数的数组。
sieve(25) # ==> [2, 3, 5, 7, 11, 13, 17, 19, 23]
这个函数的源代码可以在这里阅读:here。
我现在想重构它,使得
sieve(n)
返回第 n
个质数。但我不确定如何实现。我不想写一个完全新的更复杂的函数,所以最好的方法似乎是找出筛法应该计算到哪个值。例如,如果我要求第 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
设为这两个数之间的数字数组会导致筛法产生奇怪的值,例如第 15 个质数的结果是 56
(56 不是质数,答案应该是 47)。正如您猜想的那样,我完全不懂这个领域。如果有人能给我一些建议,我将不胜感激。
n
个元素。 - Codor