Juan Wajnerman

Juan Wajnerman

Juan is the one everybody turns to when there is a question that no one else can answer: whether Internet is down or the architecture for a massive system needs to be designed, Juan always has the correct solution. Wise and humble, he applies his vast experience with patience and pragmatism. Outside the techie world, he enjoys tennis and playing with his two kittens.

October 13, 2007

Prime generator with LINQ

Maybe this example is not impressive as an entire ray tracer in a single line, but it gives an idea of the expressiveness of LINQ.

I remember from my high school times, the internal spontaneous competitions looking for the “fastest” prime generators. We were really far from the greatest and well known prime generators, but things like that one gave us funny ways to learn interesting stuff. The algorithm used in this post is a naïve version, that has nothing to do with “fast”.

Since C# 2.0, we can write custom enumerators very easily and create “generators” like this one:

IEnumerable PositiveIntegers
{
  get {
    for (int i = 1; ; i++)
      yield return i;
  }
}

Now with LINQ, is very easy to write lazy evaluated sequences like this one:

var primes = from n in PositiveIntegers.Skip(1)
             where
                 PositiveIntegers.Skip(1)
                     .TakeWhile(x => x <= Math.Sqrt(n))
                     .All(x => (n % x) > 0)
             select n;

or even using subqueries:

var primes = from n in PositiveIntegers.Skip(1)
             where
                 (from m in PositiveIntegers.TakeWhile(x => x <= Math.Sqrt(n))
                 where m >= 2 && (n % m) == 0
                 select m).FirstOrDefault() == 0
             select n;

Now you can assume that primes contains all the infinite series of primes! In fact it’s a lazy evaluated enumerator, that searches for the next prime every time you call the MoveNext method.

So, you can search the primes less that 100:

foreach (var x in primes.TakeWhile(n => n < 100))
    Console.WriteLine(x);

the first 100 primes:

foreach (var x in primes.Take(100))
    Console.WriteLine(x);

or look for the 200th prime:

var prime200 = primes.ElementAt(200);

Of course, don't try to iterate the entire sequence ;-) .