Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Sieve Of Eratosthenes
using System;
using System.Collections.Generic;
using System.Linq;
namespace Primes
{
public static IEnumerable<int> SieveOfEratosthenes(int upperLimit)
{
int sieveBound = (upperLimit - 1) / 2,
upperSqrt = ((int)Math.Sqrt(upperLimit) - 1) / 2;
bool[] PrimeBits = new bool[sieveBound + 1];
yield return 2;
for (int i = 1; i <= upperSqrt; i++)
{
if (!PrimeBits[i])
{
yield return 2 * i + 1;
for (int j = i * 2 * (i + 1); j <= sieveBound; j += 2 * i + 1)
{
PrimeBits[j] = true;
}
}
}
for (int i = upperSqrt + 1; i <= sieveBound; i++)
{
if (!PrimeBits[i])
{
yield return 2 * i + 1;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.