Project Euler 7 Solution

Project Euler 7 & HackerRank Version Solution

Find the 10001st 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 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 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, π−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 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 with 1≤N≤10,000.

Python Source Code

  1. def prime_sieve(n):
  2. sieve = [True] * (n//2)
  3. for i in range(3,int(n**0.5)+1,2):
  4. if sieve[i//2]:
  5. sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
  6. return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
  7. # Add an extra element to the front of our list to base it from 1 and not 0
  8. prime = [0]+prime_sieve(105000)
  9. n = int(input('nth prime number (≤10001)? '))
  10. print ("Prime number", n, "is", prime[n])
download Python source code Use this link to download the Project Euler 7: Find the 10001st prime number.

Last Word