Title: Use yield to generate prime numbers in C#

This example shows how to use the yield return statement to generate prime numbers. More importantly it explains how yield return works.

You could simply loop through numbers and determine which are prime. That would be a completely sensible approach. This example uses a class that implements the IEnumerable interface instead, mostly to demonstrate that interface and the yield statement.

The example uses the following PrimeGenerator class.

public class PrimeGenerator : IEnumerable<long> { // Return true if the value is prime. private bool IsOddPrime(long value) { long sqrt = (long)Math.Sqrt(value); for (long i = 3; i <= sqrt; i += 2) if (value % i == 0) return false; // If we get here, value is prime. return true; } public IEnumerator<long> GetEnumerator() { // Start with 2. yield return 2; // Generate odd primes. for (long i = 3; ; i += 2) if (IsOddPrime(i)) yield return i; } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } }

This class implements the IEnumerable<long> interface. That means the main program can use a foreach loop to iterate over an instance of the class. I'll show that shortly.

The class first defines the IsOddPrime method, which returns true if an odd number is prime. Note that the method only works for odd inputs. The method makes variable j loop through the values 3, 5, 7, ..., up to the square root of the input value. If any of those values evenly divide into the value, then it is not prime so the method returns false. If none of those values evenly divides into the value, then it is prime and the method returns true.

The GetEnumerator<long> method implements the IEnumerable interface. One way to implement this interface is to make this method return an enumerator object that provides a Current property, and MoveNext and Reset methods. That's not too hard but it does require you to make a second class to go with this one.

This example takes a different approach. The GetEnumerator method uses the yield statement to return enumeration values. It starts by using a yield return statement to return the first prime number, 2. It then enters a loop that considers odd numbers. If the IsOddPrime method returns true for a value, the method yields that value.

If this all seems strange, it should. The yield return statement is pretty weird. Here's what happens at run time. Suppose the main program is iterating through an object's values by using a foreach loop. When the loop needs a value, it calls the GetEnumerator method. When that method uses yield return to return a value to the loop, the program remembers its current position in the method and returns to the loop. When the loop needs a new value, control returns to the previous spot in GetEnumerator and the method generates a new value.

The program continues bouncing back and forth between the foreach loop and GetEnumerator until one of three things happens. First, the program can use break, return, or some other statement to exit the foreach loop. Second, GetEnumerator can use yield break to indicate that it is done generating values. Third, GetEnumerator can end and execution can leave it.

That's how the yield statement works. Here's the code in the form's Load event handler that uses the enumerator.

// Display primes up to the indicated limit. private void btnGo_Click(object sender, EventArgs e) { long limit = long.Parse(txtLimit.Text); StringBuilder sb = new StringBuilder(); PrimeGenerator generator = new PrimeGenerator(); foreach (long value in generator) { if (value > limit) break; sb.Append(value.ToString() + " "); } string text = sb.ToString(); txtPrimes.Text = text.Substring(0, text.Length - 1); }

The code gets the limit you entered in the form's TextBox and makes a StringBuilder to hold results.

It then creates a PrimeGenerator object and uses a foreach loop to loop through the object's values. The program checks each value and breaks out of the foreach loop if it is greater than the limit. Otherwise it adds the value to the StringBuilder.

The event handler finishes by displaying the resulting string.

Download the example to experiment with it and to see additional details.