using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Program
    {
        static List<int> primes;

        static void Main(string[] args)
        {
            primes = new List<int>();

            // build our primes list
            int max = 65535;
            for (int num = 2; num < max; num++)
            {
                bool notPrime = false;
                for (int p = 0; p < primes.Count; p++)
                    if (num % primes[p] == 0) { notPrime = true; break; }
                if (notPrime) continue;

                primes.Add(num);
                Console.WriteLine(num + " is a prime.");
            }

            Console.WriteLine("there were " + primes.Count + " primes up to " + max + ".");

            Console.WriteLine("IsPrime(9001) == " + IsPrime(9001));

            Console.ReadKey();
        }

        static bool IsPrime(int value)
        {
            // primes is sorted so we can speed up the search using BinarySearch() instead of Contains()
            int index = primes.BinarySearch(value); // SO FAST
            if (index < 0) return false;
            return true;
        }
    }
}