Project Euler Problem 7: 10001st prime

Back to primes! So far we’ve been able to get away with being a little greedy with our compute when playing with primes. Now Euler is ratcheting up the difficulty and we’ll have to focus on efficiency.

As usual, if you haven’t spent time with Problem 7 yet, take a chance to play with it on your own and come back.

TODO

Counting Primes

Let’s start by looking at each integer, deciding whether it’s prime, and counting it if it is until we get to the 10,001st prime.

Our first stab at an is_prime(n) function will be the simplest and we’ll iterate into more optimized (and complicated) versions after. Here’s the starting point:

def is_prime(n):
    for x in range(2, n):
        if n % x == 0:
            return False
    return True

This is almost good enough to solve the problem in under a minute. My laptop chugs through the first 10,001 primes in 68 seconds using that version of the is_prime(n) function (full code later). But we can do better.

Looking back at our Problem 3 Solution we optimized our is_prime(n) function by checking only numbers up to $ \sqrt{n} $. Check out that post if you want to dig deep into why / how that works.

def is_prime(n):
    for x in range(2, math.floor(math.sqrt(n)) + 1):
        if n % x == 0:
            return False
    return True

This runs a lot faster. It finds the 10,001st prime in 0.37 seconds. But can we make it even better?

[Perhaps the most rediscovered result about primes numbers] (https://primes.utm.edu/notes/faq/six.html) is the fact that every prime bigger than 3 is “next” to a multiple of 6. That is, every prime number is either 1 greater than or 1 less than 6 * k for some k. Using that property we can skip the 2/3rds of the integers. In code:

def is_prime(n):
    if n == 2 or n == 3:
      return True
    for x in range(6, math.floor(math.sqrt(n), 6) + 1):
        if n % x == 0:
            return False
    return True

That definition takes advantage of Python’s “step” argument to the range() function. We’re looking at every multiple of 6 (below our limit) and checking whether the number before and after it is prime

That optimi

seen = 0
n = 1
while seen < 10001:
    n += 1
    if is_prime(n):
        seen += 1

print(n)

See an issue on this page? Report a typo, bug, or give general feedback on GitHub.

Grae Drake
Grae Drake
Advisor

I build mission-driven products, teams, and companies.

Related