Create a gist now

Instantly share code, notes, and snippets.

Eratostene Sieve
using System.Collections;
using System.Collections.Generic;
namespace Eratostene
{
/**
* Compute Prime Numbers
*
* Example:
<code>
var eratostene = new Eratostene(1000);
eratostene.Crivello();
var primes = eratostene.GetPrimes();
var howMany = eratostene.GetNumberOfPrimes();
Console.WriteLine($"Found {howMany} primes.");
foreach (var prime in primes)
{
Console.WriteLine($"> {prime}");
}
</code>
**/
public class Eratostene
{
private readonly int _maxPrime;
private readonly BitArray _sieve;
public Eratostene(int count)
{
this._maxPrime = count;
this._sieve = new BitArray(count, true)
{
[0] = false,
[1] = false
};
}
public bool IsPrime(int number)
{
return this._sieve[number];
}
public List<int> GetPrimes()
{
var retPrimes = new List<int>();
for (var k = 0; k < this._maxPrime; k++)
{
if (this._sieve[k])
{
retPrimes.Add(k);
}
}
return retPrimes;
}
public int GetNumberOfPrimes()
{
var count = 0;
for (var k = 0; k < this._maxPrime; k++)
{
if (this._sieve[k])
count++;
}
return count;
}
public void Crivello()
{
var currPrime = this.NextPrime(0);
while (currPrime*currPrime < this._maxPrime)
{
var i = currPrime*currPrime;
while (i < this._maxPrime)
{
this._sieve[i] = false;
i += currPrime;
}
currPrime = this.NextPrime(currPrime);
}
}
private int NextPrime(int lastPrime)
{
for (var j = lastPrime + 1; j < this._maxPrime; j++)
{
if (this._sieve[j])
{
return j;
}
}
return 0;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment