13,558,244 members
Alternative Article
alternative version

Stats

21.9K views
15 bookmarked
Posted 12 Sep 2012
Licenced CPOL

Finding Prime Numbers

, 14 Sep 2012
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:

```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 `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

Share

 Software Developer (Senior) Clifford Nelson Consulting 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.

You may also be interested in...

 Pro

 First PrevNext
 BitArray vs. BitVector Kenneth Haugland14-Sep-12 12:00 Kenneth Haugland 14-Sep-12 12:00
 Re: BitArray vs. BitVector Clifford Nelson14-Sep-12 13:55 Clifford Nelson 14-Sep-12 13:55
 Re: BitArray vs. BitVector Kenneth Haugland14-Sep-12 14:05 Kenneth Haugland 14-Sep-12 14:05
 Re: BitArray vs. BitVector Clifford Nelson14-Sep-12 17:42 Clifford Nelson 14-Sep-12 17:42
 Re: BitArray vs. BitVector Kenneth Haugland14-Sep-12 17:54 Kenneth Haugland 14-Sep-12 17:54
 Re: BitArray vs. BitVector Kenneth Haugland16-Sep-12 8:47 Kenneth Haugland 16-Sep-12 8:47
 Ok, a new attempt :) Kenneth Haugland13-Sep-12 11:18 Kenneth Haugland 13-Sep-12 11:18
 Very neat Richard MacCutchan13-Sep-12 5:35 Richard MacCutchan 13-Sep-12 5:35
 Re: Very neat Pete O'Hanlon13-Sep-12 5:49 Pete O'Hanlon 13-Sep-12 5:49
 Re: Very neat Richard MacCutchan13-Sep-12 5:57 Richard MacCutchan 13-Sep-12 5:57
 Re: Very neat Clifford Nelson13-Sep-12 6:06 Clifford Nelson 13-Sep-12 6:06
 Re: Very neat Richard MacCutchan13-Sep-12 6:25 Richard MacCutchan 13-Sep-12 6:25
 Re: Very neat Clifford Nelson13-Sep-12 6:39 Clifford Nelson 13-Sep-12 6:39
 Re: Very neat Richard MacCutchan13-Sep-12 23:04 Richard MacCutchan 13-Sep-12 23:04
 Re: Very neat Pete O'Hanlon13-Sep-12 6:13 Pete O'Hanlon 13-Sep-12 6:13
 Re: Very neat Richard MacCutchan13-Sep-12 6:24 Richard MacCutchan 13-Sep-12 6:24
 Re: Very neat [modified] Ravi Bhavnani14-Sep-12 11:08 Ravi Bhavnani 14-Sep-12 11:08
 Re: Very neat [modified] Clifford Nelson14-Sep-12 11:54 Clifford Nelson 14-Sep-12 11:54
 Re: Very neat [modified] Ravi Bhavnani14-Sep-12 12:09 Ravi Bhavnani 14-Sep-12 12:09
 Re: Very neat Clifford Nelson13-Sep-12 5:57 Clifford Nelson 13-Sep-12 5:57
 Re: Very neat Kenneth Haugland13-Sep-12 6:01 Kenneth Haugland 13-Sep-12 6:01
 Re: Very neat Clifford Nelson13-Sep-12 6:13 Clifford Nelson 13-Sep-12 6:13
 Re: Very neat Richard MacCutchan13-Sep-12 6:01 Richard MacCutchan 13-Sep-12 6:01
 Re: Very neat Pete O'Hanlon13-Sep-12 6:14 Pete O'Hanlon 13-Sep-12 6:14
 Re: Very neat Clifford Nelson13-Sep-12 6:42 Clifford Nelson 13-Sep-12 6:42
 Last Visit: 31-Dec-99 18:00     Last Update: 26-May-18 0:28 Refresh 12 Next »