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