# Sieve of Eratosthenes in C#

Just because I've never written a real Sieve of Eratosthenes, I decided I should probably write one just to make sure I know what it is. I'd like (constructive) criticism on best practices, potential problems, and anything else you see fit:

static int GetNthPrime(int n)
{
List<int> primes = new List<int>() { 2, 3 };

int potentialPrime = 5;

while (primes.Count < n)
{
int squareRootPotentialPrime = (int)Math.Sqrt(potentialPrime);

for (int i = 1; i < primes.Count; i++)
{
if (potentialPrime % primes[i] == 0)
{
break;
}

if (primes[i] > squareRootPotentialPrime)
{
break;
}
}
potentialPrime += primes[0];
}

return primes[n - 1];
}

• <microoptimisation> Instead of calculating the square root and doing the comparison primes[i] > squareRootPotentialPrime, use primes[i] * primes[i] > potentialPrime. Sqrt is definitely slower than a multiplication. </microoptimisation> Mar 4 '15 at 22:44
• @WaiHaLee You can post that as an answer.
– user34073
Mar 4 '15 at 22:49

What you have written, is not exactly the Sieve of Erathostenes.
When doing the sieve, you don't do any divisions; you just step through all the numbers and cross off multiples.
The sieve doesn't find the n'th prime, but rather all primes up to a limit. This is an example of how to do the sieve. It's a very basic version.

public static IEnumerable<int> SieveOfErathostenes(int upperLimit)
{
//BitArray works just like a bool[] but takes up a lot less space.
BitArray composite = new BitArray(upperLimit);

//Only need to cross off numbers up to sqrt.
int sqrt= (int)Math.Sqrt(upperLimit);
for (int p = 2; p <= sqrt; ++p) {
if (composite[p]) continue; //The number is crossed off; skip it

yield return p; //Not crossed off means it's prime. Return it.

//Cross off each multiple of this prime
//Start at the prime squared, because lower numbers will
//have been crossed off already. No need to check them.
for (int i = p * p; i < upperLimit; i += p)
composite[i] = true;
}
//The remaining numbers not crossed off are also prime.
for (int p = sqrt + 1; p < upperLimit; ++p) {
if (!composite[p]) yield return p;
}
}


Instead of calculating the square root and doing the comparison

if ( primes[i] > squareRootPotentialPrime )


use

if ( primes[i] * primes[i] > potentialPrime )


Taking Sqrt of a floating point number will definitely be slower than a multiplication of two integers.

@duffymo states in the answer to the SO question c++ practical computational complexity of SQRT() that

...most library functions would calculate [Sqrt] using Newton's method, which converges quadratically.

Edit

I just realised that the integer multiplication happens inside the loop over existing primes, whereas the Sqrt happens outside. Once the number of existing primes reaches a threshold (I don't know when), my suggestion will be slower than the original. Instead, I propose the following:

    int squareRootLargestPrime = (int)Math.Sqrt(5);
while ( primes.Count < n )
{
for ( int i = 1; i < primes.Count; i++ )
{
// elided

if ( primes[i] > squareRootLargestPrime )
{
squareRootLargestPrime = (int)Math.Sqrt(potentialPrime);
break;
}


That way you only use Sqrt when you get a new prime, rather than for every candidate.

Also, potentialPrime += primes[0]; feels a bit strange when primes[0] is always 2.

As mentioned by others, your code is not really a sieve. For examples of fast, memory efficient sieves, I refer you to:

Sieve31 for 31 bit primes, i.e. int. Finds over 105 million primes.

Sieve32 for 32 bit primes, i.e. uint. Finds over 203 million primes.

A BitArray uses far less memory than a List<int>.
The BitArray can be even smaller by only tracking the odd numbers.
You definitely don't want to put sluggish operations, e.g. Sqrt inside a loop if you can avoid it.
Sieve31.Primes(int.MaxValue).ToList().