Sieve of Eratosthenes in C#

Question

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)
            {
                primes.Add(potentialPrime);
                break;
            }
        }
        potentialPrime += primes[0];
    }

    return primes[n - 1];
}

Answer 1

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;
    }
}

Answer 2

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 )
            {
                primes.Add(potentialPrime);
                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.

Answer 3

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.

Constructive Comments

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.

The purpose of a sieve it to step off multiples of known prime. Even that doesn't require multiplying as much as incrementing by that prime. What you have is a fancier naive trial-by-division.

My Sieve31 would take around 30 seconds, returns all 105 found primes, and probably fits in a list, e.g.

Sieve31.Primes(int.MaxValue).ToList().