Problem 7 asks: “What is the 10,001st prime number?”
I spent a lot of time trying to work out a way to determine a range of numbers small enough to yeild any nth prime number, and started to write up the paragraphs that follow. What I found was that primes are tricky and will betray you! Joking aside, I did find some interesting “nth prime” approximation information that is worth sharing:
There are quite a few ways to go about approximating the number of primes less than a sufficiently large number. Check out Wolfram’s entry on prime counting functions: http://mathworld.wolfram.com/PrimeCountingFunction.html. If we know some n, then we know approximately how many primes are less than n by the following approximation
This is the flip side to what we really need to know, and try as I might I could not get the algebra to work out to determine which n fulfilled n/ln(n) = 10,001. However, I was pretty certain this was the idea of what I was looking for, so I searched again for known prime inequalities. Again, Wolfram served up useful info: http://functions.wolfram.com/NumberTheoryFunctions/Prime/29/0002/. This is the relationship I was looking for:
Using this inequality we can narrow down our search for the 10,001st prime to a manageable window of possibilities.
Unfortunately the window of primes was quite large no matter which inequality I used (there are tighter bounds known), and since I hadn’t iterated to get my shortcut I had no way of knowing which prime was the 10001st. Nonetheless, knowing the upper bound of the 10001st prime will let me use an algorithm from an early Project Euler problem – the Euclid/Erastothenes Sieve! Codepad is throwing timeout errors, but you can see the code, sans results, here: http://codepad.org/UbhpCbQW
Update: I made some minor code changes that turned into significant performance boosts, but Codepad is still timing out. Here’s the new paste: http://codepad.org/jTHJ5gkY
bowdenc 