Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / C#
Alternative
Article

Finding Prime Numbers

Rate me:
Please Sign up or sign in to vote.
4.67/5 (12 votes)
14 Sep 2012CPOL3 min read 33.3K   19   29
This is an alternative for "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:

C#
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:
C#
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior) Clifford Nelson Consulting
United States United States
Has been working as a C# developer on contract for the last several years, including 3 years at Microsoft. Previously worked with Visual Basic and Microsoft Access VBA, and have developed code for Word, Excel and Outlook. Started working with WPF in 2007 when part of the Microsoft WPF team. For the last eight years has been working primarily as a senior WPF/C# and Silverlight/C# developer. Currently working as WPF developer with BioNano Genomics in San Diego, CA redesigning their UI for their camera system. he can be reached at qck1@hotmail.com.

Comments and Discussions

 
QuestionBitArray vs. BitVector Pin
Kenneth Haugland14-Sep-12 12:00
mvaKenneth Haugland14-Sep-12 12:00 
AnswerRe: BitArray vs. BitVector Pin
Clifford Nelson14-Sep-12 13:55
Clifford Nelson14-Sep-12 13:55 
GeneralRe: BitArray vs. BitVector Pin
Kenneth Haugland14-Sep-12 14:05
mvaKenneth Haugland14-Sep-12 14:05 
GeneralRe: BitArray vs. BitVector Pin
Clifford Nelson14-Sep-12 17:42
Clifford Nelson14-Sep-12 17:42 
GeneralRe: BitArray vs. BitVector Pin
Kenneth Haugland14-Sep-12 17:54
mvaKenneth Haugland14-Sep-12 17:54 
QuestionRe: BitArray vs. BitVector Pin
Kenneth Haugland16-Sep-12 8:47
mvaKenneth Haugland16-Sep-12 8:47 
QuestionOk, a new attempt :) Pin
Kenneth Haugland13-Sep-12 11:18
mvaKenneth Haugland13-Sep-12 11:18 
QuestionVery neat Pin
Richard MacCutchan13-Sep-12 5:35
mveRichard MacCutchan13-Sep-12 5:35 
AnswerRe: Very neat Pin
Pete O'Hanlon13-Sep-12 5:49
subeditorPete O'Hanlon13-Sep-12 5:49 
GeneralRe: Very neat Pin
Richard MacCutchan13-Sep-12 5:57
mveRichard MacCutchan13-Sep-12 5:57 
AnswerRe: Very neat Pin
Clifford Nelson13-Sep-12 6:06
Clifford Nelson13-Sep-12 6:06 
GeneralRe: Very neat Pin
Richard MacCutchan13-Sep-12 6:25
mveRichard MacCutchan13-Sep-12 6:25 
GeneralRe: Very neat Pin
Clifford Nelson13-Sep-12 6:39
Clifford Nelson13-Sep-12 6:39 
GeneralRe: Very neat Pin
Richard MacCutchan13-Sep-12 23:04
mveRichard MacCutchan13-Sep-12 23:04 
GeneralRe: Very neat Pin
Pete O'Hanlon13-Sep-12 6:13
subeditorPete O'Hanlon13-Sep-12 6:13 
GeneralRe: Very neat Pin
Richard MacCutchan13-Sep-12 6:24
mveRichard MacCutchan13-Sep-12 6:24 
QuestionRe: Very neat [modified] Pin
Ravi Bhavnani14-Sep-12 11:08
professionalRavi Bhavnani14-Sep-12 11:08 
AnswerRe: Very neat [modified] Pin
Clifford Nelson14-Sep-12 11:54
Clifford Nelson14-Sep-12 11:54 
GeneralRe: Very neat [modified] Pin
Ravi Bhavnani14-Sep-12 12:09
professionalRavi Bhavnani14-Sep-12 12:09 
AnswerRe: Very neat Pin
Clifford Nelson13-Sep-12 5:57
Clifford Nelson13-Sep-12 5:57 
It is exactly as Pete O'Hanlon stated. LINQ is pretty cool, but unfortunately can sometimes be obscure.
GeneralRe: Very neat Pin
Kenneth Haugland13-Sep-12 6:01
mvaKenneth Haugland13-Sep-12 6:01 
AnswerRe: Very neat Pin
Clifford Nelson13-Sep-12 6:13
Clifford Nelson13-Sep-12 6:13 
GeneralRe: Very neat Pin
Richard MacCutchan13-Sep-12 6:01
mveRichard MacCutchan13-Sep-12 6:01 
GeneralRe: Very neat Pin
Pete O'Hanlon13-Sep-12 6:14
subeditorPete O'Hanlon13-Sep-12 6:14 
GeneralRe: Very neat Pin
Clifford Nelson13-Sep-12 6:42
Clifford Nelson13-Sep-12 6:42 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.