10
$\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?

1 Answers 1

13

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.

  • 2
    Wow, I can't believe I haven't run into that before.2011-06-19