Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Sieve of Eratosthenes.
public static class Eratosthenes
{
public static IEnumerable<BigInteger> Sieve(Int64 maxValue)
{
if (maxValue < 10)
{
if (maxValue == 9 || maxValue == 8 || maxValue == 7)
{
return new List<BigInteger>() { 2, 3, 5, 7 };
}
else if (maxValue == 6 || maxValue == 5)
{
return new List<BigInteger>() { 2, 3, 5 };
}
else if (maxValue == 4 || maxValue == 3)
{
return new List<BigInteger>() { 2, 3 };
}
else
{
return new List<BigInteger>() { 2 };
}
}
Int64 counter = 0;
Int64 counterStart = 3;
Int64 inc;
Int64 sqrt = 3;
Int64 ceil = maxValue >= Int64.MaxValue - 2 ? Int64.MaxValue - 2 : (Int64)maxValue;
bool[] primeMembershipArray = (bool[])Array.CreateInstance(typeof(bool), new long[] { (ceil + 2) });
primeMembershipArray[2] = true;
// Set all odds as true
for (counter = counterStart; counter <= maxValue; counter += 2)
{
if ((counter & 1) == 1) // Check if odd. &1 is the same as: %2
{
primeMembershipArray[counter] = true;
}
}
while (sqrt * sqrt <= maxValue)
{
counter = sqrt * sqrt;
inc = sqrt + sqrt;
while (counter <= maxValue)
{
primeMembershipArray[counter] = false;
counter += inc;
}
sqrt += 2;
while (!primeMembershipArray[sqrt])
{
sqrt++;
}
}
return Maths.GetRange<BigInteger>(2, maxValue).Where(l => (bool)primeMembershipArray.GetValue((Int64)l)); ;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment