Problem 7 - 10 001st Prime

Problem

This problem comes from Project Euler 7 ⤴

Problem

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?

Solution

Since we’re generating primes, I’ll be using the Sieve of Eratosthenes ⤴, which was seen and created in Problem 3.

How do we sieve 10 001 primes?

Between 1 and 100, there are 25 primes. Between 1 and 10 000, there are 1229 primes. We should be asking ourselves, “Inbetween 1 and $N$, there are 10 001 primes. What is $N$ ?” We need to ask ourselves this to have an upper limit for the Sieve of Eratosethenes.

According to the Prime Number Theorem ⤴, the density of primes between 1 and $N$ is approximately

Where $ln(N)$ is the natural logarithm of $N$ . So, the density of primes between 1 and 100 is approximately

The actual number is known to be 25%, but with a larger $N$, this becomes far more accurate. Now, the formula just gives us the density of prime numbers, and we want to know if there’s 10 001 prime numbers in $N$ . No problem, just multiply by $N$ and we get

This time, with $N = 10 000$

As mentioned, there are actually 1229 primes in between 1 and 10 000, but this isn’t too bad! Again, a larger $N$ gives us more accurate approximations.

And the number is 🥁…

With a little trial and error, we get $N = 120 000$ which should have approximately 10 260 prime numbers!

Code

# Project Euler: Problem 7
# 10001st prime

from PEF import soe

primes = soe(120000)

if (len(primes) > 10001):
    print(primes[10000])
else:
    print("Use higher number")

# PEF: Project Euler Functions

import math

def soe(n):
    '''Sieve of Eratosethenes. Finds prime numbers'''

    primes = []
    number_list = [True]*(n+1)

    for i in range(2, n+1):
        if number_list[i]:
            primes.append(i)

            # Eliminate multiples. They aren't prime
            for multiple in range(i**2, n+1, i):
                number_list[multiple] = False
    
    return primes