Project Euler Problem 7 Solution

Project Euler Problem 7 Statement

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?

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 N^th 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, π⁻¹(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

Solves all test cases for Hackerrank Project Euler Problem 7

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])

Run Project Euler Problem 7 using Python on replit.com.

Last Word

If we wanted the 100,001^st 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,001^st 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.