// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (15 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 7 Solution

Project Euler 7 Solution

Project Euler 7: Find the 10001st prime number


Problem Description

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?

Analysis

I wanted a solution that would solve both this problem and the HackerRank.com version of Project Euler 7 which queries hundreds of nth prime numbers. So, the quickest and easiest way is simply to generate enough primes as a list and use it’s index (or ordinal position – 10001 in this example) to find the answer. The prime generator featured here is fast and can generate 20 million primes in less than one-half second.

Since our prime sieve function generates prime numbers below some limit, it’s prudent to make this limit as close to our biggest nth prime as possible to conserve resources. 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.

There is a handy calculator here and a table here if you want to learn more about the prime counting function, π(x), and how to determine a reasonable limit.

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank


Project Euler 7 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 7 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|104743|

Afterthoughts

  • Function prime_sieve is listed in Common Functions and Routines for Project Euler
  • If this problem were to ask for the 100,001st prime number, then using the calculator mentioned above, we would need to generate all primes less than 1,300,000 to make sure it was included. The answer would be 1,299,721.
  • Calculating prime numbers is a recurring theme throughout Project Euler so you may want to add this function to your library to help solve other problems.
Project Euler 7 Solution last updated

Discussion

No comments yet.

Post a comment