My friend and colleague Justin Etheredge posted a LINQ challenge to promote his new TekPub series on mastering LINQ. Justin is wicked smart and a fantastic teacher; it promises to be a good series.
The challenge is to produce “a single LINQ query which starts with Enumerable.Range(1,n) and produces a list of prime numbers from the range.” In other words:
var primes = Enumerable.Range(1, SomePositiveValue).SomeLinqMethod(
Of course, being a seasoned lazy developer, my instinct was to search for a prime number algorithm in another language, ideally a functional language, and port it to C#. I found algorithms similar to Nenad Markovic’s clever solution to this challenge:
public IEnumerable<int> ExpectedGetPrimes(int max)
{
return Enumerable.Range(1, max).Where(n => Enumerable.Range(1, n).Where(m => (n / m) * m == n).Count() == 2);
}
It’s clean, and I’m using it to verify my algorithm below. I like the algorithm, because it’s the definition prime number translated into code: exactly two natural number divisors: 1 and itself. It was obvious the algorithm was counting the factors, but it actually took me a minute to really grok that n and m are integers. Thus division remainders are truncated, e.g., (5/2)*2 equals 4 not 5.
Yes, I can be dense at times, and to be honest, it would have taken me a while to write that algorithm. That is just not how my brain works. When I need high performance algorithms, I turn to Google or a more mathematically minded colleague.
In the spirit of the challenge, I decided to to solve this problem in a novel way, i.e., a solution not copied from something else. So this is what I came up with:
public IEnumerable<int> MyGetPrimes(int max)
{
return Enumerable.Range(1, max).Skip(1).Reverse()
.Aggregate(new List<int>(), (result, value) =>
{
result.RemoveAll(n => n % value == 0);
result.Add(value);
return result;
});
}
It’s not pretty, but it works. I’m just reversing the sequence and creating a new list. As I add each number, I’m removing any existing elements for which the current number is a factor. It’s slow, and I would never use it in production code. And to get the output in the right order (not a criterion for the challenge), you have to reverse it again. However, it does pass the tests, and technically it could be written on one line, if you have a 30" screen.