I was browsing the Internet yesterday when, god knows how, I found a cool way to generate prime numbers[1]:

The Incomprehensible Word of Unpronouncable Name The Sieve of Eratosthenes[2].

Suppose you want to find all primes between 1 and 100.

  1. Start by assuming that all numbers are prime.
  2. When you encounter a prime, mark all its multiples (up until 100) as non-prime.
  3. Repeat until you reach 100.
  4. Find all numbers that haven't been marked as "non-prime"; these are your prime numbers (duh).

This performs much, much better than a brute force attack.

C gives me a headache, so I decided to create a C# version of the prime-number generator: 


public static IntList FindPrimes(int max, out System.TimeSpan elapsed)
{
    if (max < 2)
    {
        throw new System.ArgumentException(
            "Max candidates needs to be greater than 2.", "max");               
    }

    DateTime start = DateTime.Now;
    IntList primes = new IntList();
    BitArray candidates = new BitArray(max, true);

    Debug.Assert(candidates != null && candidates.Length > 0, 
        "Candidates array hasn't been initialized properly.");

    for (int i = 2; i < max; i++)
    {
        if (candidates[i] == false)
        {
            // Multiples of non-primes are also 
            // multiples of some primes, which 
            // means that we already marked them 
            // as non-primes. 
            continue;
        }

        primes.Add(i);

        for (int j = i * 2; j < max; j += i)
        {
            // Mark multiples as non-primes 
            candidates[j] = false;
        }
    }

    System.DateTime end = System.DateTime.Now;

    elapsed = end - start;

    return primes;
}

Download PrimeNumberGenerator.cs