/*

10001st prime

​

Problem 7

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 10001 st prime number?

*/

​

using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        int num = 10001;

        uint nthPrime = GetNthPrime(num);

        Console.WriteLine($"{num} th prime number is {nthPrime}");

    }

    private static uint GetNthPrime(int num = 10001)

    {

        IList<uint> primes = new List<uint>() { 2 };

        for ( uint n = 3 ; primes.Count <= num - 1 ; n += 2 )

        {

            bool isPrime = true;

            foreach ( int p in primes )

            {

                if ( n % p == 0 )

                {

                    isPrime = false;

                    break;

                }

                if ( p * p > n )

                {

                    break;

                }

            }

            if ( isPrime )

            {

                primes.Add(n);

            }

        }

        return primes[num - 1];

    }

    private static bool[] SieveOfEratosthenes(int num)

    {

        if (num <= 1)

        {

            return new bool[0];

        }

        bool[] primeCheck = new bool[num + 1];

        for ( int n = 0 ; n < num ; n++ )

        {

            primeCheck[n] = true;

        }

        for ( int n = 2 ; n * n <= num ; n++ )

        {

            if ( primeCheck[n] == true )

            {

                for ( int p = n * n ; p <= num ; p += n )

                {

                    primeCheck[p] = false;

                }

            }

        }

        return primeCheck;

    }

}