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?
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 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*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 = +prime_sieve(105000)
- n = int(input('nth prime number (≤10001)? '))
- print ("Prime number", n, "is", prime[n])
prime_sievefunction is available in the repl.it window by clicking the files icon in the top left corner.
- 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.