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

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.)

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