Problem 7: 10001st prime

Problem:

Please find the problem here.

Solution:
It seems that the number go a little larger from the previous problem at around 100, to now at around 10,000. With a computer, however, 10,000 is still a fairly small number, especially so if you have linear/quadratic algorithms. We will still brute force it. Let's first estimate how big would that prime be.

We know that prime density decreases and is governed by the prime number theorem. Let's use it to estimate how big would the 10001st prime be.

Assuming 10,000 is a large number (far from true), so we have
$
\begin{eqnarray*} \pi(x) &=& \frac{x}{\ln(x)} \\ 10001 &=& \frac{x}{\ln(x)} \end{eqnarray*} $

That is a non-linear equation to solve - in general - it is hard to solve non-linear equation - but we are just estimating, so let do some wild guess.

When $ x = 10000, \frac{x}{\ln(x)} = 1083 $
When $ x = 100000, \frac{x}{\ln(x)} = 8685 $
When $ x = 120000, \frac{x}{\ln(x)} = 10260 $

So we estimate the prime number to be around 100,000 - 120,000, this is fairly small and we will just try the numbers 1 by 1. Here is the code:

namespace Euler
{
    using System;
    using System.Collections.Generic;

    internal static partial class Program
    {
        public static void Problem007()
        {
            List<int> primes = new List<int>();
            int primeCount = 0;
            int current = 2;
            while (true)
            {
                bool isPrime = true;
                foreach (int prime in primes)
                {
                    if (current % prime == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    primes.Add(current);
                    primeCount++;
                    if (primeCount == 10001)
                    {
                        Console.WriteLine(current);
                        return;
                    }
                }
                current++;
            }
        }
    }
}

The code is trivial - except it did a simple smart thing - to certify a number is prime, all we need to check is that any prime smaller than it is not a factor of it. That cut the number of trial division significantly.

Answer: 104743.

Note how close our estimate based on prime number theorem is.