using System;
using System.Collections.Generic;
using System.Text;

namespace euler7
{
    //Find the 10001st prime
    class Program
    {
        private static List<long> _staPrimes;

        static void Main(string[] args)
        {
            int n = 10001;

             //Brutal and dumb prime searcher
            _staPrimes = new List<long>();
            _staPrimes.Add(2);
            _staPrimes.Add(3);

            long inc = 4;
            //Hint #0: start with 3 then consider only odd numbers (remove multiples of 2)
            //Hint #1: start with 5 then increments by 2 then 4 (remove multiples of 2 and 3)
            for (long i = 5; _staPrimes.Count != n; i += inc)
            {
                isPrime(i);
                if (inc == 2) inc = 4; else inc = 2;
            }

            Console.WriteLine(n + "th prime is: " + _staPrimes[n-1].ToString());
            Console.ReadLine();
        }
    
        private static bool isPrime(long i)
        {
            //Hint #2: Compare only with primes up to the sqrt of the candidate
            for (int j = 0;( (j < _staPrimes.Count) && (_staPrimes[j] * _staPrimes[j] <= i)); ++j)
            {
                if (i % _staPrimes[j] == 0)
                    return false;
            }
            _staPrimes.Add(i);
            return true;
        }
    }
}