Project Euler 7 Solution with Python

Project Euler 7 & HackerRank Version Solution

Find the 10001^st prime number

by {BetaProjects} | MAY 12, 2009 | Project Euler & HackerRank

Project Euler 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 fast and can generate 20 million primes in less than one–half second. But, it generates prime numbers below some numerical upper bound and not a specific number of primes. Calling our function as prime_sieve(10001) will return a list of all primes below 10,001 or 1,229 prime numbers. We are, therefore, left with the task of calculating our upper bound to include at least 10,001 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 calculator reports that there are 10,024 primes less than 105,000 which cover both this problem and the HackerRank version.

HackerRank version

Extended to solve all test cases for Project Euler 7

HackerRank Project Euler 7 runs 1,000 test cases with 1≤N≤10,000.

Python Source Code

def prime_sieve(n):
sieve = [True] * (n//2)
for i in range(3,int(n**0.5)+1,2):
if sieve[i//2]:
sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
# Add an extra element to the front of our list to base it from 1 and not 0
prime = [0]+prime_sieve(105000)
n = int(input('nth prime number (≤10001)? '))
print ("Prime number", n, "is", prime[n])

Use this link to download the Project Euler 7: Find the 10001^st prime number.

Run Project Euler 7 using Python on repl.it

Last Word

The prime_sieve function is available in the repl.it window by clicking the files icon in the top left corner.
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.