Project Euler 7: Find the 10001st prime number

---

Problem Description

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 simply to generate enough primes as a list and use it’s index (or ordinal position – 10001 in this example) to find the answer. The prime generator featured here is fast and can generate 20 million primes in less than one-half second.

Since our prime sieve function generates prime numbers below some 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.

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

This program and method
solves all test cases
on HackerRank

Project Euler 7 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 7 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.

Afterthoughts

• Function prime_sieve is listed in Common Functions and Routines for Project Euler
  
• 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 to make sure it was included. The answer would be 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.