Title: Use LINQ to find prime numbers in C# (Part 1 of 3)

This example uses LINQ to find prime numbers between 1 and a maximum value that you enter. It defines the following IsPrime method to determine whether a number is prime.

// Return true if the number is prime. private bool IsPrime(int number) { if (number < 2) return false; if (number == 2) return true; if (number % 2 == 0) return false; for (int i = 3; i * i <= number; i += 2) if (number % i == 0) return false; return true; }

If the number is less than 2, then the number is not prime so the method returns false.

If the number equals 2, then the number is prime so the method returns true.

If the number is evenly divisible by 2, then the number is even (and not 2) so it is not prime and the method returns false.

Finally, to handle the more interesting case, the program considers odd values i starting at 3. As long as i squared is less than or equal to number, then i might be a factor of number. If i divides number evenly, then i is a factor so number is not prime and the method returns false.

If none of the odd i values divides number evenly, then number is prime and the method returns true.

Now the program can use the IsPrime method to find prime numbers. When you click the Go button, the following code executes.

// Find primes. private void btnGo_Click(object sender, EventArgs e) { int max = int.Parse(txtMax.Text); // Examine numbers to find primes. var primes = from number in Enumerable.Range(1, max) where IsPrime(number) select number; // Display the results. lstPrimes.DataSource = primes.ToList(); }

First, the code gets max, the maximum number that you want to consider. It then defines a LINQ query.

The query examines numbers chosen from Enumerable.Range(1, max). The Enumerable.Range method generates a sequence of numbers starting at an intitial value (1 in this example) and containing a given number of values (this example's range contains max values).

The query's where clause picks the values for which the IsPrime method returns true. The select clause selects the values that pass the where clause's filter.

The result is a query that returns an IEnumerable containing the prime numbers between 1 and max. The program calls the query's ToList method to copy the results into a List and displays the results in the program's ListBox.

This example is relatively straightforward, but it's not terribly efficient, largely because the LINQ query considers lots of even numbers that you know are not prime. In my next post I'll show how to make this query more efficient.

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