using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Test
{
        public static void Main()
        {
            var pgm = new Test();
            pgm.DoStuff();
            Console.WriteLine("Done. Press Enter.");
            Console.ReadLine();
        }

        private void DoStuff()
        {
            const int MaxPrime = 
                1000000; 
                // 22307;
            for (var i = 0; i < 2; ++i)
            {
                var sw = Stopwatch.StartNew();
                var primes = FindPrimes(MaxPrime);
                sw.Stop();
                var ms = (1000.0*sw.ElapsedTicks)/Stopwatch.Frequency;
                Console.WriteLine("{0:N0} primes found in {1} ms ({2})", primes.Count, ms, sw.ElapsedMilliseconds);
            }
            Console.WriteLine();
        }

        private List<int> FindPrimes(int maxVal)
        {
            var primes = new List<int>{2};
            for (var x = 3; x <= maxVal; x += 2 )
            {
                var maxDiv = (int) Math.Round(Math.Sqrt(x));
                bool isPrime = true;
                for (var i = 1; i < primes.Count && primes[i] <= maxDiv; ++i)
                {
                    if ((x%primes[i]) == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    primes.Add(x);
                }
            }
            return primes;
        }
}