If you guys are really interested in this kind of thing, look up how RSA security is done.  It's based on the fact that you can determine if a number is prime very quickly, but you can't factor a number into primes very quickly.  So, your keys are really large randomly determined prime numbers (like 128 bits or larger) that are used together to encode your message.  The NSA has a standing money reward for anyone that can come up with a fast method for factoring numbers because that will break most of the encryption used today.  The NSA also has HUGE supercomputers they use to just crunch through and decipher secure messages if they don't use a large enough number of bits in the keys.  I recommend 1024 for anyone who cares, it would take years to decode.

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

namespace LinqTest
{
    class Program
    {
        static void Main(string[] args)
        {
            List allNumbers = new List();
            int numbersToSearchTo = 1000000;
            var allNumbersVar = System.Query.Sequence.Range(2, numbersToSearchTo - 1);

            allNumbers = allNumbersVar.ToList();

            for (int div = 2; div < Math.Sqrt(numbersToSearchTo); div++)
            {
                var numbers = from num in allNumbers
                              where num % div != 0 || div >= num
                              select num;

                allNumbers = numbers.ToList();
            }
        }
    }
}

I don't like LINQ because to me it is bloated technology, it is also not nearly as fast (still runs in 1 thousandth of a second but alot slower) as my previous solution, but I thouhgt I would share.

All I have to say is holy crap my math is rusty!  I have been far too ingrained into Windows programming related to business logic nad not enough math problems! 

It doesn't return 8. I think its broken.

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

namespace Primes
{
    internal class Program
    {
        //-- This executes on my machine in: 00:00:00.0021929

        private static int maxPrime = 1000000;
        private static bool[] numbers;
        private static List primes;
        private static int squareRootOfMaxPrime;

        private static void Main()
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();

            List primeNumbers = GetPrimes();

            sw.Stop();

            TimeSpan ts = sw.Elapsed;
            Console.WriteLine("Time: {0}", ts);
            Console.ReadLine();
        }

        private static List GetPrimes()
        {
            squareRootOfMaxPrime = (int)Math.Sqrt(maxPrime);
            numbers = new bool[maxPrime >> 1];
            int maxPossiblePrimesLessThanN = (int)(1.1 * (maxPrime / Math.Log(maxPrime)));
            primes = new List(maxPossiblePrimesLessThanN);
            PopulatePrimes();
            return primes;
        }

        private static void PopulatePrimes()
        {
            primes.Add(2);
            for (int i = 3; i < maxPrime; i += 2)
            {
                int bitOffset = (i - 1) >> 1;
                if (!numbers[bitOffset])
                {
                    ScratchOffMultiplesOfThePrime(i, i << 1);
                    primes.Add(i);
                }
            }
        }

        private static void ScratchOffMultiplesOfThePrime(int prime, int addend)
        {
            if (prime > squareRootOfMaxPrime)
            {
                return;
            }
            for (int i = prime * prime; i < maxPrime; i += addend)
            {
                int bitOffset = (i - 1) >> 1;
                numbers[bitOffset] = true;
            }
        }
    }
}

Yep I am using the Sieve Of Eratosthenes implementation, I am rewritting a full example with extra functionality as we speak because work can be boring :P