Project Euler - Problem 7: 10001st Prime

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 10,001st prime number?

---

Explanation

The simplest way to do this is to bruteforce it. We'll start a collection of primes and start iterating over the odd numbers (because 2 eliminates even numbers as potential prime candidates - super small optimization that removes half the numbers). We will test all of these numbers with our collection of prime numbers, if any of them are divisible by them they are not prime and will not be added to the collection.

Another solution is to generate all of the numbers and then remove all of the numbers that are divisible, this will leave you with only prime numbers. This is called the Sieve of Eratosthenes.

Solutions #1:

private static void Problem7()
{
  List primes = new List()
  {
      2, 3
  };
  int limit = 10001;
  int value = 5;

  while(primes.Count < limit)
  {
      bool isPrime = true;
      foreach(int prime in primes)
      {
          if(value % prime == 0)
          {
              isPrime = false;
          }
      }
      
      if(isPrime)
      {
          primes.Add(value);
      }
      value += 2;
  }
  Console.WriteLine(primes[primes.Count - 1]);
}

An online sample of which can be found here.

The average tick time for this was around 20,000,000 ticks. Not very performant at all.

Solution #2:

We can drastically improve this by adding a break statement to exit out of the for loop when we know the number is not prime.

private static void Problem7()
{
  List primes = new List()
  {
      2, 3
  };
  int limit = 10001;
  int value = 5;

  while(primes.Count < limit)
  {
      bool isPrime = true;
      foreach(int prime in primes)
      {
          if(value % prime == 0)
          {
              isPrime = false;
              break;
          }
      }
      
      if(isPrime)
      {
          primes.Add(value);
      }
      value += 2;
  }
  Console.WriteLine(primes[primes.Count - 1]);
}

An online sample of which can be found here.

The average tick time for this was 4,450,000 ticks. We could also refactor the function so that we could remove the flag - it could look something like this:

private static bool IsPrime(int number, List primes)
{
    foreach(int prime in primes)
    {
        if(number % prime == 0)
        {
            return false;
        }
    }
    return true;
}

There is also proof that states there are infinitely many primes. There is a variation on this proof that can show all primes come in the form of 6k +/- 1. A proof of this can be found here that would limit the amount of numbers we would need to check.

Solution #3:

We'll start by allocating a bit sieve for whether a location is prime or not. Then we'll start marking them off as we go to determine our list of primes.

private static void Problem7()
{
    int limit = 10001;
    bool[] sieve = new bool[limit*limit];
    int prime = 2;
    int primeCount = 1;
    
    while(primeCount < limit)
    {
        int location = prime;
        while(location + prime < sieve.Length)
        {
            location += prime;
            sieve[location - 1] = true;
        }
        
        // Look for the next prime to sieve.
        location = IncrementPrime(prime);
        while(location < sieve.Length && sieve[location - 1] == true)
        {
            location = IncrementPrime(location);
        }
        
        if(location < sieve.Length)
        {
            prime = location;
            primeCount++;
        }
    }
    
    Console.WriteLine(prime);
}

private static int IncrementPrime(int prime)
{
    if(prime % 2 == 0)
    {
        return prime + 1;
    }
    else
    {
        return prime + 2;
    }
}

An online sample of which can be found here.

I'm not convinced I've done this the most efficient way, but this is how a sieve could look. The execution tick times are along the same lines as the original solution.

We could optimize this by removing half the sample size by excluding 2. We could also improve the size if we can figure out a way to reduce the overall size of the sieve. As it stands, if we were to use very large numbers I'm not convinced the limit by limit bounds will be sufficient. I couldn't come up with a better limit for the upperbound, if you know of one - let me know.

Summary:

The sieve is another way to think about the problem, but can be a little more tedious to implement because it is not how humans think about the problem naturally. The straightforward method was relatively quick and easy to implement, which further shows how usually the simplest approach can be best. If you have a better solution to the sieve, let me know.