Project Euler Problem 7 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
The quickest and easiest way to solve both this problem and the HackerRank version is to build a list of prime numbers. We can use that list’s index (or ordinal position) to find the Nth prime number. The only concern is to make sure we generate enough prime numbers to satisfy all the queries.
Our prime number generator is highly efficient, capable of generating primes up to 20 million in under half a second. However, it works by generating all primes below a given numerical upper bound, not by producing a specific number of primes. For example, calling prime_sieve(10001) will generate all primes less than 10,001, yielding a list of 1,229 primes.
Prime counting function
The Prime Counting Function, π(x) gives the number of primes less than or equal to a given number x. So, the inverse, π−1(n), takes a number of primes and gives us an x, which is the upper bound used for our prime_sieve() function. For more information, there is a calculator here: The Nth Prime Page.
The calculator reports that there are 10,024 primes less than 105,000 which cover both this problem and the HackerRank version.
HackerRank version
HackerRank Project Euler 7 runs 1,000 test cases to find prime numbers within a limit, 1≤N≤10,000.
Python Source Code
import Euler
primes = Euler.prime_sieve(105000)
for _ in range(int(input())):
print(primes[int(input())-1]) 
Last Word
- If we wanted the 100,001st prime number, then, according to our calculator, we would need to generate primes less than 1,300,000. This would calculate 100,021 prime numbers and enough to include our target. After generating those prime numbers we can easily find the 100,001st prime as 1,299,721.
- The prime_sieve function will be imported instead of hard coded into the source code. This provides flexibility to include different sieves as required to solve a problem.