Project Euler 7 Problem 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?
This solution will solve both this problem and the HackerRank version of Project Euler 7. So, the quickest and easiest way is to simply generate enough primes into a list and use its index (or ordinal position) to find the answer. The prime generator featured here is fast and can generate 20 million primes in less than one-half second.
from Euler import prime_sieve print prime_sieve(105000) #10000 and not 10001 because the list is zero-based #105000 so we have at least 10001 prime numbers
The extra list element,
, prepended to the
prime list is to allow the nth prime to be the nth element without having to worry about the list starting from 0.
The prime sieve function generates prime numbers below some numerical limit. Therefore, it’s prudent to make this limit as close to our biggest nth prime as possible.
Prime counting function
The inverse of the Prime Counting Function generates a good guess. This function takes a number, n, and calculates the number of primes below it. So, the inverse takes a number of primes and tells us how high our limit must be to include them. The calculator reports that there are 10,024 primes less than 105,000 which covers both this problem and the HackerRank version.
HackerRank queries 1,000 Nth prime numbers, with N ≤ 10,000.
Python 2.7 Source
If we wanted the 100,001st prime number, then we would need to generate all primes less than 1,300,000. This would calculate 100,021 prime numbers and enough to include our target. The 100,001st prime is 1,299,721.