Problem 7: 10001st Prime

By listing the first six prime numbers: $2, 3, 5, 7, 11$, and $13$, we can see that the $6$th prime is $13$.

What is the $10\,001$st prime number?

Solution Approach

To solve this efficiently, we can use the Sieve of Eratosthenes, a classical algorithm for finding all prime numbers up to a given limit. The sieve marks multiples of each prime starting from 2 as composite, leaving only primes unmarked.

However, before we begin, we need an estimate for how far we must search to reach the 10001st prime. Using the Prime Number Theorem:

$$p_n \approx n (\ln n + \ln(\ln n))$$

For $n = 10001$:

$$p_{10001} \approx 10001 (9.21 + 2.22) \approx 114,000$$

This means we can safely search up to about 120,000 to find the 10001st prime.

In terms of python:

We can use a simple sieve to generate all primes up to this limit and then pick the 10001st one:


import math
n = 10001
limit = int(n * (math.log(n) + math.log(math.log(n)))) + 10
sieve = [True] * limit
sieve[0:2] = [False, False]
for i in range(2, int(limit ** 0.5) + 1):
    if sieve[i]:
        sieve[i*i : limit : i] = [False] * len(range(i*i, limit, i))
    
primes = [i for i, is_prime in enumerate(sieve) if is_prime]
print(primes[n - 1])

Explained line by line:

We start by importing the math library to use logarithmic functions.
We set n to 10001, the index of the prime we want to find.
We calculate an upper limit for our sieve using the Prime Number Theorem and add a small buffer.
We create a list called sieve initialized to True, indicating that all numbers are initially assumed to be prime. We set the first two entries (0 and 1) to False since they are not prime.
We then iterate through each number starting from 2 up to the square root of the limit. For each prime number found, we mark all its multiples as False (not prime).
After constructing the sieve, we create a list of all indices that are still marked as True, which correspond to prime numbers.
Finally, we print the 10001st prime by accessing the appropriate index in the list of primes.

Running the above code leads to an answer of $104743$