Project Euler: Problem 7

Problem 7

Approach - Sieve of Eratosthenes

Since we're only looking for the 10,001st prime, we could probably check each number for primeness until we found the 10,001st one. But I've never implemented a prime sieve before and that sounds more interesting.

The Sieve of Eratosthenes is probably the most well known and I'm sure it will work fine for this problem.

This works via process of elimination. Let's say you wanted to find all the primes less than 100. Then, starting with 2, you eliminate all the multiples of 2 up to 100 (4, 6, 8, 10 etc.). Repeat for multiples of 3 (6, 9, 12, 15 etc). It's only necessary to iterate the numbers <= sqrt(N). So for N = 100, the stopping point would be 10.

The tricky thing here is that we don't initially know how large of an N to choose. I.e., I'm not able to guess with much confidence if the 10,001st prime is bigger or smaller than say 1,000,000.

There are some ways to guess this though. The simplest being the prime number theorem

There are two useful ways to look at the prime number theorem. One is that it can give us a lower bound for the nth prime. The other is that we can estimate the number of primes that are less than or equal to a number. Those two formulas:

1. $n^{th} prime \geq n \cdot \ln(n)$

   The lower bound for the nth prime is n * ln(n)

2. $prime(n) \approx \cfrac{n}{ln(n)}$

   The number of primes less than n is approximately n / ln(n)

So in our search for the 10,001st prime, we can determine that the lower bound is 92,114 (10,001 * ln(10,001)).

And furthermore, the number of primes less than 120,000 is approximately 10,260 (120,000 / ln(120,000)). 120,000 was just the first round number where the total number that I tried where the total number of primes is higher than our target (10,000 < 10,260). So we should be able to find the 10,001st prime by setting the ceiling of our search space to 120,000.

JS Solution

Conclusion

Final answer

$104743$