Primes, Sieve of Eratosthenes

// See Knuth's TAOCP section 4.5.4 exercise 8.
// The number of primes less then or equal to n: 
// http://primes.utm.edu/howmany.shtml 
// pi(n) <= n/ln(n)*(1+1.27262/ln(n))
// A fast sieve:
// http://www.primzahlen.de/files/referent/kw/sieb.htm
// (Pentium III 550 Mhz, C/C++, n=10^9, 2.533 s!)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
class Program
{
    private static Stopwatch sw = new Stopwatch();
    static void Main()
    {
        int n = 1;
        while (n <= 1000000000)             // primes.exe n=10^9 23 s. 
        {
            sw.Restart();
            int[] primes = getPrimes(n);
            sw.Stop();
            Console.WriteLine("n: " + n + "  primes: " + primes.Length +
                              " in " + sw.ElapsedMilliseconds + " ms");
            n *= 10;
        }
        Console.ReadLine();
    }
    private static int[] getPrimes(int n)
    {
        List<int> primes = new List<int>();
        if (n < 2) return primes.ToArray();
        double log_n = Math.Log(n);
        primes.Capacity = (int)((n / log_n) * (1 + 1.2762 / log_n));
        n = ((n & 1) + n) >> 1;
        BitArray x = new BitArray(n + 1);
        int i = 4, p = 3, q = 4;
        for (; q < n; q += p >> 1 << 2)
        {
            if (!x[q])
            {
                x[q] = true;
                for (i = q + p; i < n; i += p) x[i] = true;
            }
            p += 2;
        }
        primes.Add(2);
        for (i = 1; i < n; i++) if (!x[i]) primes.Add(i * 2 | 1);
        return primes.ToArray();
    }
}