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?
There are libraries that list out the prime numbers, and I make full use of them in my solutions to other problems. As with the other early problems, however, this one is still worth doing the hard way to gain experience. My favored approach is by far the oldest: the sieve of Eratosthenes.
Initially, every number between 2 and \(n\) is marked as a potential prime. Then 2 is added to a list of primes, and all higher multiples of 2 are marked as composite, beginning with 4. Next, 3 is added to the list, and all higher multiples of 3 are marked as composite, beginning with 9. 4 is skipped because it's already been marked. 5 is unmarked, so we add it to the list and mark all its multiples, beginning with 25. We proceed in this vein until the list is exhausted.
This approach works because when we begin examining a number \(p\), we know that all multiples of every prime less than \(p\) have already been marked; thus, if \(p\) is unmarked, it is not divisible by any smaller prime, and is therefore prime itself.
The only remaining issue is to identify a proper cap on the numbers to sieve through. From the Prime Number Theorem, we know that if \(p_k\) is the \(k\)-th prime number, then \(k \approx \frac{p_k}{\ln p_k}\) for large enough \(k\) (thanks once again to a young Gauss). A reasonable approach is to take progressive multiples \(c\) of \(k\) until \(\frac c{\ln c} > k\), which doesn't take long because of how slowly \(\ln\) grows; in our case, \(c\) ends up being \(120012\), which is a healthy margin above the actual value \(p_k = 104743\).
from math import log
def p7(k=10001):
c = k
while c / log(c) < k:
c += k
sieve = [i > 1 for i in range(c)]
found = 0
for p in range(2, c):
if sieve[p]: # p is prime
found += 1
if found == k:
return p
for m in range(p ** 2, c, p):
sieve[m] = False