BitArray

using System;
using System.Collections;
using System.Collections.Generic;

public static class Sieve
{
    public static IEnumerable<int> Primes(int max)
    {
        if (max < 0)
            throw new ArgumentOutOfRangeException(nameof(max));

        var primes = new BitArray(max + 1, true);

        for (var i = 2; i <= max; i++)
        {
            if (!primes[i])
                continue;

            for (var j = i * 2; j <= max; j += i)
                primes[j] = false;

            yield return i;
        }
    }
}

The first step is to check the input for validity:

if (max < 0)
    throw new ArgumentOutOfRangeException(nameof(max));

We then create a [BitArray][hash-set] that will contain the numbers that are a multiple of the primes we find:

var primes = new BitArray(max + 1, true);

The BitArray constructor takes two values:

1. The number of items it should hold (in our case, max + 1 as counting starts at 0)
2. The initial value of all items (true in our case)

This will allocate just enough memory to hold max + 1 bits, with their initial value set to true (which is the bit value of 1).

We'll then use this bit array to represent our sieve. For any prime we find, we'll change the value for all its multiples to false, which we can then use to skip those numbers later on.

Let's look at an example to see how this would work. If we take 9 as the maximum value, our initial BitArray's content look something like this:

Index: 0123456789
Value: 1111111111

Now if we start at index 2 (which is prime) and then cross off its multiples (setting them to false), we get:

Index: 0123456789
Value: 1111010101

You can see how the numbers at index 4, 6 and 8 have all had their value set to false, essentially crossing them off as possible primes.

We then move to index 3, which value is true so it must be a prime. Crossing off its multiples (6, which was already crossed off, and 9) gives us:

Index: 0123456789
Value: 1111010100

We then check index 4, which value is false and thus can't be a prime so we'll skip it and move to the next number, until we've iterated over all numbers up to max.

Let's see how to implement this.

First, we start iterating from 2 (the smallest prime) up until the maximum that was specified:

for (var i = 2; i <= max; i++)

Within the loop, our first check is to see if the value at index i (our current number) is false, which means that it must be a multiple of a prime. It thus can't be a prime and we'll skip the number:

if (!primes[i])
    continue;

If this check returns false, we're dealing with a prime! This means that we can then cross off any multiples of this prime, which we can do with another (nested) for-loop:

for (var j = i * 2; j <= max; j += i)
    primes[j] = false;

Note how we start at the first multiple of the prime (i * 2) and that we increment the loop iterator variable by the prime number (j += i) to iterate over all the multiples of the prime.

The final step is to return the prime number, for which we use a yield statement:

yield return i;

Note that even though we yield an indidivual integer, what is returned from a caller's viewpoint is a sequence of integers.