11
$\begingroup$

I'm helping my son with Project Euler and we're working on problem 7, "What is the 10001st prime number?" We'll use a Sieve of Eratosthenes and we'll increase the size of the initial array until we're left with 10001 primes. We'll start with a pretty big array and increase it by whatever seems reasonable, since there is no time constraint, until we get the answer.

My question is, is there a way to make an informed guess about the size of the initial array?

$\endgroup$

1 Answer 1

14
$\begingroup$

Wikipedia gives the bounds $n \ln n + n(\ln\ln n - 1) < p_n < n \ln n + n \ln \ln n$, where $p_n$ is the $n$th prime. So the $10001$st prime is between 104318 and 114320.

$\endgroup$
1
  • 2
    $\begingroup$ Wow, I can't believe I haven't run into that before. $\endgroup$
    – uncle brad
    Jun 19, 2011 at 13:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .