我如何使用埃氏筛法得到第n个质数？

Question

我如何使用埃氏筛法得到第n个质数？

5

我已经编写了一个名为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）。

正如您猜想的那样，我完全不懂这个领域。如果有人能给我一些建议，我将不胜感激。

- GreenTriangle

2

你不应该要求它在任何区间内生成质数。整个算法是基于它发现了在某一点之前的所有质数后才进行下一步的知识构建的。你需要要求它从1到上限找出所有的质数。 - Lasse V. Karlsen

以下方法是否可行？使用您在问题中提到的上限（但我不知道为什么它是正确的），生成所有小于该上限的质数，并返回列表的第n个元素。 - Codor

@Codor 我本以为这样会起作用，但结果非常奇怪，我不理解。如果我将初始列表设置为2到上限，一开始可以得到质数，但之后就只是一个稳定的计数器——267、268、269、270、271等等。这太奇怪了。 - GreenTriangle

1

不要列出在这些范围内的质数，而是使用筛法函数计算小于上限的质数，然后计数到所需的质数。如果得到非质数，则您的筛法函数是不正确的。 - user448810

1

@GreenTriangle 这不是我想要的；我的意思是保留埃拉托斯特尼筛法，但将上限作为参数使用（即从零开始生成所有素数，直到上限），然后从埃拉托斯特尼筛法的结果中返回所需的条目。 - Codor

@Codor 哦，我的错误。我现在明白你的意思了，你是完全正确的，这是一个聪明的解决方案。感谢您的贡献，您的想法非常好。 - GreenTriangle

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MvG · Accepted Answer

埃拉托色尼筛法必须始于开端；不能在任意区间筛选，否则会漏掉所有更小的质数。因此，您不必关心下限，只需要关注上限。您已经给出了上限，并且Wikipedia也证实了这一点：

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

因此，只需采用该界限，插入您的n并迭代直到找到n个质数。如果边界合理紧密，则您的筛子通常会略微偏大，但不会太大，我预计这将是情况。

点击这里查看该边界的表格或这里查看绘图。顺便说一下，创建表格的代码也在执行相同的操作。我想至少有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多个素数，接下来我可以向您展示计算出的界限与实际值的比较。