Finding Prime Numbers

Introduction

I recently answered a question on C# forum about an algorithm for the Sieve of Eratosthenes. The person asking the question had actually done a brute force implementation of finding all primes, and wanted to know how to better implement it since the calculation was taking forever. I actually solved the problem much more efficiently by improving the algorithm, and going to an Array of bool instead of a List of instantiated classes, and then looked up what was published. I had a bit faster algorithm than the one on the paper I found, so published an alternative version. This presents a faster algorithm for finding prime numbers using Sieve of Eratosthenes.

The Code

I used a simple Array of bool for numbers since this should have the best performance (KISS). It had to be initialized to true since the algorithm starts with true instead of false; I could improve the performance slightly by starting with false values. Basically, the algorithm starts from 2, a prime:

1. Sets all entries of the array of Boolean that have an index of a number that are a multiple of a prime to false.
2. Finds the next prime by looking for the next lowest index value that is still true.
3. If the next found prime is less than the square root of the numbers to analyze, then stop, otherwise repeat step 1.

The criteria for stopping is when the square root of the number to be checked if they are prime because we know that any non-prime number that has not been found will have to have factors that are greater than the last processed prime, or the prime that would be next processed times itself. This algorithm is implemented in the Run method below:

class Program
{
  private static bool[] _numbers;
  private const int Count = 1000000000;

  static void Main(string[] args)
  {
    Console.WriteLine("Maximum number checked if prime: " + (Count - 1).ToString("n0"));
    var sw = new Stopwatch();
    sw.Start();
    Run();
    sw.Stop();
    Console.WriteLine("Milliseconds to run algorithm: " + sw.ElapsedMilliseconds);

    sw.Reset();
    sw.Start();
    Console.WriteLine("Primes: " + _numbers.Count(i => i).ToString("n0"));
    sw.Stop();
    Console.WriteLine("Milliseconds using LINQ Count: " + sw.ElapsedMilliseconds);

    sw.Reset();
    sw.Start();
    Console.WriteLine("Primes: " + _numbers.Sum(i => i ? 1 : 0).ToString("n0"));
    sw.Stop();
    Console.WriteLine("Milliseconds using LINQ Sum: " + sw.ElapsedMilliseconds);

    sw.Reset();
    sw.Start();
    Int64 sum = 0;
    for (int i = 2; i < _numbers.Count(); i++)
      if (_numbers[i]) sum += i;
    Console.WriteLine("Sum of Primes: " + sum.ToString("n0"));
    sw.Stop();
    Console.WriteLine("Milliseconds for sum of Primes: " + sw.ElapsedMilliseconds);

    Console.WriteLine("Primes:");
    for (int i = 0; i < 100; i++)
      if (_numbers[i]) Console.WriteLine("   " + i);

    Console.ReadLine();
  }

  private static void Run()
  {
    _numbers = new bool[Count];
    for (int i = 2; i < Count; i++)
      _numbers[i] = true;

    int baseCounter = 1;
    int countLimit = (int)Math.Sqrt(Count);
    while (baseCounter < countLimit)
    {
      do
      {
        baseCounter++;
        if (baseCounter == Count) return;
      } while (!_numbers[baseCounter]);

      int counter = baseCounter << 1;
      while (counter < Count)
      {
        _numbers[counter] = false;
        counter += baseCounter;
      }
    }
  }
}

Notes

• Originally, I implemented this algorithm so that it processed all primes. Putting in the criteria of ending the processing on the square root of the number of numbers to be analysed the processing time dropped from 40 milliseconds to 24 milliseconds.
• I also replaced the bool Array with a BitArray (see this link). This increases the processing time by about 50%. However, I ran out of memory with the method using the bool Array at between 1.15 and 1.2 trillion, whereas could get to over 2 trillion with a BitArray (limited by the max size of the BitArray which takes an int argument). In fact, I could process 1 trillion primes with an array of Boolean and a BitArray. Here is the code for the BitArray:

private static void RunBitArray()
{
  const int count = 1000000000;
  var _numbers = new BitArray(count);
  for (int i = 2; i < count; i++)
    _numbers[i] = true;

  int baseCounter = 1;
  int countLimit = (int)Math.Sqrt(count);

  while (baseCounter < countLimit)
  {
    do
    {
      baseCounter++;
      if (baseCounter == count) return;
    } while (!_numbers[baseCounter]);

    int counter = baseCounter << 1;
    while (counter < count)
    {
      _numbers[counter] = false;
      counter += baseCounter;
    }
  }
}

• I did calculations on the time it takes to do the count using a LINQ Count method, and it was about 80% of the time to find the primes. Using a Sum LINQ statement instead of the Count took slightly more time.

History

• 09/13/2012: Fixed ending criteria for loop to be the square root of the count. This is because any number that is left that is not a prime would have to be the current "baseCounter" times the "baseCounter" + 2.
• 09/14/2012: Major rewrite to include different options