PrimeThing.cs

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

namespace TestThing {
    public interface IPrimeTest {
        IEnumerable<int> CalculatePrimes(int max);
    }

    public class JuniorTest : IPrimeTest {
        public IEnumerable<int> CalculatePrimes(int max) {
            List<int> primes = new List<int>();

            for(int i = 2; i <= max; i++) {
                bool isPrime = true;
                for(int j = 2; j < i; j++) {
                    if(i % j == 0) isPrime = false;
                }

                if(isPrime) primes.Add(i);
            }

            return primes;
        }
    }

    public class JuniorTestOptimized : IPrimeTest {
        public IEnumerable<int> CalculatePrimes(int max) {
            List<int> primes = new List<int>();

            for(int i = 2; i <= max; i++) {
                bool isPrime = true;
                for(int j = 2; j < i; j++) {
                    if(i % j == 0) {
                        isPrime = false;
                        break;
                    }
                }

                if(isPrime) primes.Add(i);
            }

            return primes;
        }
    }

    public class ShortCircuitTest : IPrimeTest {
        public IEnumerable<int> CalculatePrimes(int max) {
            List<int> primes = new List<int>();

            for(int i = 2; i <= max; i++) {
                if(i == 2) {
                    primes.Add(i);
                    continue;
                }

                if(i % 2 == 0) continue;

                bool isPrime = true;
                for(int j = 3; j < i; j += 2) {
                    if(i % j == 0) {
                        isPrime = false;
                        break;
                    }
                }

                if(isPrime) primes.Add(i);
            }
            return primes;
        }
    }

    public class SieveTest : IPrimeTest {
        public IEnumerable<int> CalculatePrimes(int max) {
            List<int> primes = new List<int> { 2 };

            int half = (max - 1) >> 1;
            BitArray nums = new BitArray(half, false);
            int sqrt = (int)Math.Sqrt(max);

            for(int i = 3; i <= sqrt;) {
                for(int j = ((i * i) >> 1) - 1; j < half; j += i) {
                    nums[j] = true;
                }

                do {
                    i += 2;
                } while(i <= sqrt && nums[(i >> 1) - 1]);
            }

            for(int i = 0; i < half; i++) {
                if(!nums[i]) primes.Add((i << 1) + 3);
            }

            return primes;
        }
    }

    public class Program {
        public static void Test(IPrimeTest test, int max) {
            List<TimeSpan> times = new List<TimeSpan>();
            for(int i = 0; i < 5; i++) {
                Stopwatch sw = Stopwatch.StartNew();
                IEnumerable<int> primes = test.CalculatePrimes(max);
                sw.Stop();

                if(i > 0) times.Add(sw.Elapsed);
                Console.WriteLine("{0} {1}:\t {2} primes in {3}", test.GetType().Name, i, primes.Count(), sw.Elapsed);
            }

            double averageTicks = times.Average(t => t.Ticks);
            Console.WriteLine("Average: {0}\n", new TimeSpan(Convert.ToInt64(averageTicks)));
        }

        public static void Main(string[] args) {
            const int testSize = 100000;

            Test(new JuniorTest(), testSize);
            Test(new JuniorTestOptimized(), testSize);
            Test(new ShortCircuitTest(), testSize);
            Test(new SieveTest(), testSize);

            Console.ReadKey();
        }
    }
}