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&lsqb;i&rsqb; == 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