如何使用埃拉托色尼的筛来获得的第n个质数？ [英] How can I use the Sieve of Eratosthenes to get the nth prime?

问题描述

我写了一个函数，筛（N），使用埃拉托色尼的筛返回所有质数的数组高达ñ 。

I've written a function, sieve(n), that uses the Sieve of Eratosthenes to return an array of all primes up to n.

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

源出于此功能，可以阅读这里。

我想现在重构这让筛（N）将返回 N 个素数。我只是不知道我怎么会做到这一点。我不想写一个全新的更复杂的功能，所以它似乎是最好的方法是要弄清楚什么样的价值筛应该数到。

I want to refactor this now so that sieve(n) will return the nth prime. I'm just not sure about how I'd do that. I don't want to write an entirely new more elaborate function, so it seems like the best method is to figure out what value the sieve should count up to.

例如，如果我问的第27届总理，整数的筛子的初步名单应在2至的（这是我知道的第27届黄金不大于）的。但有一个制定出什么样的价值是简单的方式？

For example, if I ask for the 27th prime, the sieve's initial list of integers should be 2 up to (something I know the 27th prime isn't greater than). But is there a simple way to work out what that value is?

我研究这个问题，并找到<一href="http://www.quora.com/What-are-good-ways-to-find-nth-prime-number-in-the-fastest-way/answer/Jason-Martin"相对=nofollow>这个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 是红宝石的自然对数），而只是让列表数这两个数字之间的阵列使筛产量怪异的值，例如 56 第15届黄金（56不是素数，答案应该是47）。

I researched this question and found this Quora post which said that the nth prime must be between n*Math.log(n) + n*(Math.log(Math.log(n))-1) and n*Math.log(n) + n*Math.log(Math.log(n)) (where Math.log is Ruby for the natural logarithm), but simply making list an array of numbers between those two figures makes the sieve yield weird values, like 56 for the 15th prime (56 is not prime and the answer should be 47).

正如您可以猜到，我完全出在这里我的元素。如果有人可以给我一些建议，我真的AP preciate吧。

As you can guess, I'm totally out of my element here. If someone could offer me some advice I'd really appreciate it.

推荐答案

埃拉托色尼的筛子总是要从头开始;你不能筛在一些任意的间隔，因为你会失去所有小素数。所以，你不必去关心一个下限，只为一个上限。你给了，并维基百科证实：

The sieve of Eratosthenes always has to start from the beginning; you can't sieve in some arbitrary interval since you'd loose all smaller primes. So you don't have to care for a lower bound, only for an upper bound. Which you gave, and which Wikipedia confirms:

P <子> N ＆LT; N LN（ N LN N ）的 N ≥6

p_n < n ln (n ln n) for n ≥ 6

所以，简单地采取束缚，插上你的 N 和重复，直到你发现 N 的素数。您筛通常会有点太大了，但不要太多，如果绑定的是合理的紧，我希望是这样。

So simply take that bound, plug in your n and iterate till you have found n primes. Your sieve will usually be a bit too big, but not too much if the bound is reasonably tight, which I expect to be the case.

请参阅这里为绑定或表<一个href="http://www.wolframalpha.com/input/?i=parametric%20plot%20%7Bn*ln%28n*ln%28n%29%29%2CPrime[floor%28n%29]%7D%2C%7Bn%2C2%2C100%7D"相对=nofollow>这里的阴谋。顺便说一句，在code创建表做同样的事情。我想至少有500个条目，所以我计算

See here for a table of that bound or here for a plot. By the way, the code creating the table is doing the same thing. I wanted at least 500 entries, so I computed

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个素数出来的，为此，我那么可以告诉你如何计算势必比较实际值。

and got a bit over 500 primes out of it, for which I then could show you how the computed bound compares to the actual value.

这篇关于如何使用埃拉托色尼的筛来获得的第n个质数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！