# HashSet

Sieve in C#
``````using System;
using System.Collections.Generic;

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

var primeMultiples = new HashSet<int>();

for (var i = 2; i <= max; i++)
{
if (primeMultiples.Contains(i))
continue;

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

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 `HashSet<int>` that will contain the numbers that are a multiple of the primes we find:

``````var primeMultiples = new HashSet<int>();
``````

We then 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 current number (`i`) is a multiple of one of the primes we found. If so, we'll skip the number as it can't be a prime:

``````if (primeMultiples.Contains(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)
``````

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.

Note

When a `yield` statement is written, the compiler transforms the method into a state machine that is suspended after each yield statement.

Note

Methods that use a `yield` statement are also lazy, which means that calling `Sequence(number)` by itself does not do anything. It is only when a method is called that forces evaluation (like `Count()` or `ToArray()`), that we're forcing iteration over the elements in the sequence.

29th May 2024 · Found it useful?

## Other Approaches to Sieve in C#

Other ways our community solved this exercise