Project Euler 7: Find the 10001st prime number

Project Euler 7 Problem Description

Project Euler 7: 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 10001^st prime number?

Analysis

I wanted a solution that would solve both this problem and the HackerRank.com version of Project Euler 7 which queries hundreds of nth prime numbers. So, the quickest and easiest way is to simply generate enough primes into a list and use it’s index (or ordinal position) to find the answer. The prime generator featured here is fast and can generate 20 million primes in less than one-half second.

The extra list element, [0], prepended to the prime list is to allow the nth prime to be the nth element without having to worry about the list starting from 0.

from Euler import prime_sieve
print prime_sieve(105000)[10000]
#10000 and not 10001 because the list is zero-based
#105000 so we have at least 10001 prime numbers

Since our prime sieve function generates prime numbers below some numerical limit, it’s prudent to make this limit as close to our biggest nth prime as possible to conserve resources. The inverse of the Prime Counting Function generates a good guess. This function takes a number, n, and calculates the number of primes below it, so the inverse takes a number of primes and tells us how high our limit must be to include them. The calculator reports that there are 10,024 primes less than 105,000 which covers both this problem and the HackerRank version.

There is a handy calculator here and a table here if you want to learn more about the prime counting function, tragically named π(x), and how to determine a reasonable limit.

This program and method
solves all test cases for
Project Euler 7 on HackerRank

Project Euler 7 Solution

Afterthoughts

• Function prime_sieve is listed in Common Functions and Routines for Project Euler. The function is also included here in the second Trinket tab named “Euler.py” next to the “main.py” tab.
  
• If this problem were to ask for the 100,001st prime number, then using the calculator mentioned above, we would need to generate all primes less than 1,300,000 (which calculates 100,021 primes) to make sure it was included. The 100,001st prime is 1,299,721.
  
• Calculating prime numbers is a recurring theme throughout Project Euler so you may want to add this function to your library to help solve other problems.