Select Page

Project Euler 7 Problem Statement

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?

Solution

This solution will solve both this problem and the HackerRank version of Project Euler 7. So, the quickest and easiest way is to simply generate enough primes into a list and use its 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.

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

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.

The prime sieve function generates prime numbers below some numerical limit. Therefore, it’s prudent to make this limit as close to our biggest nth prime as possible.

Prime counting function

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, named π(x), and how to determine a reasonable limit.

HackerRank version

HackerRank queries 1,000 Nth prime numbers, with N ≤ 10,000.

Python 2.7 Source

Last Word

If we wanted the 100,001st prime number, then we would need to generate all primes less than 1,300,000. This would calculate 100,021 prime numbers and enough to include our target. The 100,001st prime is 1,299,721.