Instantly share code, notes, and snippets.

# guildenstern70/eratostene.cs Created Nov 17, 2015

Eratostene Sieve
 using System.Collections; using System.Collections.Generic; namespace Eratostene { /** * Compute Prime Numbers * * Example: 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}"); } **/ 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 GetPrimes() { var retPrimes = new List(); 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; } } }