#7 - 10001st prime
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10,001st prime number?
Because the crux of the problem is to find a specific prime, I will not be using the primesieve package, as it trivially gives us the answer. Instead, for this problem, we can create a sieve, where we mark off composite numbers in a list. The sieve requires an upper bound, which is not immediately clear based on the number. According to the Prime number theorem, an upper bound for the $n$th prime number $p_n$ is \[p_n < n(\ln n + \ln \ln n)\]
Substituting $n = 10001$, we get that $p_{10001} < 114319.2$. This is how far the sieve has to go.
The sieve itself is straightforward to generate. Originally, we assume every number starting with 2 is prime. If we encounter a number that is marked as prime, then we mark all multiples of that number as composite. Then, we move to the next number that is marked as prime. At the end of the process, we have a full list of which numbers are prime. To speed things up a little bit, we start counting from the end.
# file: "problem007.py"
import math
n = 10001
limit = int(n * (math.log(n) + math.log(math.log(n))))
sieve = [True] * (limit + 1)
# By definition, 0 and 1 are not primes.
sieve[0] = False
sieve[1] = False
# Start at index 2, so the index = prime number
p = 2
while p < limit + 1:
# If it's composite, then go to the next one
if not sieve[p]:
p += 1
continue
# Mark all multiples
for i in range(2 * p, limit + 1, p):
sieve[i] = False
p += 1
# Since this is an upper bound, count the number of prime numbers,
# and count backwards from the end...
num_primes = sum(sieve)
encountered = 0
i = limit
while encountered < num_primes - n + 1:
if sieve[i]:
encountered += 1
i -= 1
# i got subtracted by 1, so add one back to get the actual location
print(i + 1)
Running this loop, we get
104743
0.06304600000112259 seconds.
Thus, 104743 is the 10,001st prime.
