# Finding Prime Numbers

By , 14 Sep 2012

## 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);

}

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

 Clifford Nelson Software Developer (Senior) ETeam/Delloitte United States Member
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 PIMCO in Newport Beach, CA.

Votes of 3 or less require a comment

Hint: For improved responsiveness ensure Javascript is enabled and choose 'Normal' from the Layout dropdown and hit 'Update'.
 Search this forum Profile popups    Spacing RelaxedCompactTight   Noise Very HighHighMediumLowVery Low   Layout Open AllThread ViewNo JavascriptPreview   Per page 102550
 First PrevNext
 BitArray vs. BitVector Kenneth Haugland 14 Sep '12 - 12:00
 Re: BitArray vs. BitVector Clifford Nelson 14 Sep '12 - 13:55
 Re: BitArray vs. BitVector Kenneth Haugland 14 Sep '12 - 14:05
 Re: BitArray vs. BitVector Clifford Nelson 14 Sep '12 - 17:42
 Re: BitArray vs. BitVector Kenneth Haugland 14 Sep '12 - 17:54
 Re: BitArray vs. BitVector Kenneth Haugland 16 Sep '12 - 8:47
 Ok, a new attempt :) Kenneth Haugland 13 Sep '12 - 11:18
 Very neat Richard MacCutchan 13 Sep '12 - 5:35
 Re: Very neat Pete O'Hanlon 13 Sep '12 - 5:49
 Re: Very neat Richard MacCutchan 13 Sep '12 - 5:57
 That's what I thought, but I still don't quite see where `i` comes from or why you cannot just say `_numbers.Count(true)`. I guess I need to read the MSDN section on Lambdas again (and again ...). One of these days I'm going to think of a really clever signature. Sign In·View Thread·Permalink
 Re: Very neat Clifford Nelson 13 Sep '12 - 6:06
 Re: Very neat Richard MacCutchan 13 Sep '12 - 6:25
 Re: Very neat Clifford Nelson 13 Sep '12 - 6:39
 Re: Very neat Richard MacCutchan 13 Sep '12 - 23:04
 Re: Very neat Pete O'Hanlon 13 Sep '12 - 6:13
 Re: Very neat Richard MacCutchan 13 Sep '12 - 6:24
 Re: Very neat [modified] Ravi Bhavnani 14 Sep '12 - 11:08
 Re: Very neat [modified] Clifford Nelson 14 Sep '12 - 11:54
 Re: Very neat [modified] Ravi Bhavnani 14 Sep '12 - 12:09
 Re: Very neat Clifford Nelson 13 Sep '12 - 5:57
 Re: Very neat Kenneth Haugland 13 Sep '12 - 6:01
 Re: Very neat Clifford Nelson 13 Sep '12 - 6:13
 Re: Very neat Richard MacCutchan 13 Sep '12 - 6:01
 Re: Very neat Pete O'Hanlon 13 Sep '12 - 6:14
 Re: Very neat Clifford Nelson 13 Sep '12 - 6:42
 Last Visit: 31 Dec '99 - 18:00     Last Update: 21 May '13 - 0:46 Refresh 12 Next »