The previous post showed how you can use LINQ to find prime numbers. For every number between 1 and a maximum, the LINQ query called the `IsPrime` method to see if the number should be part of the selection.

That works, but it’s pretty inefficient because half of the numbers it examines are even. That means roughly half of the calls to `IsPrime` are wasted work.

This example uses the following code to check only the odd numbers between 1 and the maximum. It also uses a lambda expression instead of a separate `IsPrime` method.

// Find primes. private void btnGo_Click(object sender, EventArgs e) { int max = int.Parse(txtMax.Text); // Define the IsOddPrime delegate. Func<int, bool> IsOddPrime = n => { for (int i = 3; i * i <= n; i += 2) if (n % i == 0) return false; return true; }; // Check odd numbers. var primes = from number in Enumerable.Range(1, max / 2) where IsOddPrime(2 * number + 1) select 2 * number + 1; // Add the number 2. List<int> numbers = primes.ToList(); numbers.Insert(0, 2); // Remove max + 1 if it is in the list. if (numbers[numbers.Count - 1] > max) numbers.RemoveAt(numbers.Count - 1); // Display the results. lstPrimes.DataSource = numbers; }

The code gets the maximum value you entered as in the previous example. It then defines the delegate variable `IsOddPrime`. It sets this variable equal to a statement lambda that determines whether an odd number greater than 1 is prime. Because it assumes the number is odd and greater than 1, it skips test that the previous version of the program had to make.

The statement lambda considers odd values `i` starting at 3. As long as `i` squared is less than or equal to the number in question, then `i` might be a factor of the number. If `i` divides the number evenly, then `i` is a factor so the number is not prime and the method returns `false`.

If none of the values of `i` evenly divide the number, then the lambda returns `true`.

Having initialized the `IsOddPrime` variable, the code uses it in a LINQ query. This time the query loops over a range that starts at 1 and contains `max / 2` values. For each value `i`, the query examines 2 * `i` + 1. As `i` covers the range, 2 * `i` + 1 covers odd values between 3 and `max` + 1. The query uses `IsOddPrime` to see if 2 * `i` + 1 is prime and, if it is, selects it.

This query has two problems. First, it doesn’t include 2 as a prime. To solve that problem, the program adds 2 at the beginning of the result list.

The second problem is that the loop considers the value `max` + 1. If that result happens to be a prime, it gets added to the list even though it is greater than `max`. You can either ignore this or remove that value as shown in the code above.

The code finishes by displaying the prime numbers.

This code runs much faster than the previous version because it considers roughly half as many numbers as candidate primes. In practice you won’t notice much difference unless you are selecting a lot of primes. Perhaps up to 10 million or so.

In my next post, I’ll show how to make this query more LINQ-like. (Although the version shown here may be the best because it’s just as fast and easier to understand.)

Pingback: Use LINQ with an embedded lambda expression to find prime numbers in C# (Part 3 of 3) - C# HelperC# Helper