Click here to Skip to main content
Click here to Skip to main content
Alternative Article

Finding Prime Numbers

, 14 Sep 2012 CPOL
Rate this:
Please Sign up or sign in to vote.
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 Boolean 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 Boolean 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 Boolean 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 Boolean 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

License

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

Share

About the Author

Clifford Nelson
Software Developer (Senior) ETeam/Delloitte
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 three years has been working primarily as a senior WPF/C# and Silverlight/C# developer. Currently working as WPF developer with NBC Universal in Universal City, CA

Comments and Discussions

 
GeneralMy vote of 5 PinmemberArash M. Dehghani12-Jul-13 1:29 
QuestionBitArray vs. BitVector PinmemberKenneth Haugland14-Sep-12 13:00 
AnswerRe: BitArray vs. BitVector PinmemberClifford Nelson14-Sep-12 14:55 
GeneralRe: BitArray vs. BitVector PinmemberKenneth Haugland14-Sep-12 15:05 
GeneralRe: BitArray vs. BitVector PinmemberClifford Nelson14-Sep-12 18:42 
GeneralRe: BitArray vs. BitVector PinmemberKenneth Haugland14-Sep-12 18:54 
QuestionRe: BitArray vs. BitVector PinmemberKenneth Haugland16-Sep-12 9:47 
QuestionOk, a new attempt :) PinmemberKenneth Haugland13-Sep-12 12:18 
QuestionVery neat PinmvpRichard MacCutchan13-Sep-12 6:35 
AnswerRe: Very neat PinprotectorPete O'Hanlon13-Sep-12 6:49 
GeneralRe: Very neat PinmvpRichard MacCutchan13-Sep-12 6:57 
AnswerRe: Very neat PinmemberClifford Nelson13-Sep-12 7:06 
GeneralRe: Very neat PinmvpRichard MacCutchan13-Sep-12 7:25 
GeneralRe: Very neat PinmemberClifford Nelson13-Sep-12 7:39 
GeneralRe: Very neat PinmvpRichard MacCutchan14-Sep-12 0:04 
GeneralRe: Very neat PinprotectorPete O'Hanlon13-Sep-12 7:13 
GeneralRe: Very neat PinmvpRichard MacCutchan13-Sep-12 7:24 
QuestionRe: Very neat [modified] PinmemberRavi Bhavnani14-Sep-12 12:08 
AnswerRe: Very neat [modified] PinmemberClifford Nelson14-Sep-12 12:54 
GeneralRe: Very neat [modified] PinmemberRavi Bhavnani14-Sep-12 13:09 
AnswerRe: Very neat PinmemberClifford Nelson13-Sep-12 6:57 
GeneralRe: Very neat PinmemberKenneth Haugland13-Sep-12 7:01 
AnswerRe: Very neat PinmemberClifford Nelson13-Sep-12 7:13 
GeneralRe: Very neat PinmvpRichard MacCutchan13-Sep-12 7:01 
GeneralRe: Very neat PinprotectorPete O'Hanlon13-Sep-12 7:14 
GeneralRe: Very neat PinmemberClifford Nelson13-Sep-12 7:42 
QuestionThank you PinmemberAlbarhami13-Sep-12 5:10 
GeneralMy vote of 3 [modified] PinmemberAlbarhami13-Sep-12 5:10 
GeneralRe: My vote of 3 PinmemberClifford Nelson13-Sep-12 7:45 
QuestionToo bad... PinmemberKenneth Haugland13-Sep-12 0:12 

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

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

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.1411023.1 | Last Updated 15 Sep 2012
Article Copyright 2012 by Clifford Nelson
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid