Project Euler

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