How can I use the Sieve of Eratosthenes to get the nth prime?

Question

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]

The source for this function can be read here.

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.

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?

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).

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

Answer 1

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 < n ln (n ln n) for n ≥ 6

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.

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]

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.