Project Euler 7: Find the 10001st prime number
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 10001st prime number?
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.
solves all test cases
Project Euler 7 SolutionRuns < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 7 Solution Python 2.7 source.
AnswerSlowly 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.
prime_sieveis 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.