Project Euler and Linq

First I’d like to thank Stefaan for introducing me to Project Euler. Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

Most of the problems you can brute force in resonable time, but the challenge is more of a personal level in trying to solve them elegant or in as few lines as possible.

I quickly found that the magic of yield return and Linq was well suited to solve several of the problems I’ve encountered yet. So I decided to write a blog post about them and share my new-found knowlege of Linq.

Problem 1: Add all the natural numbers below one thousand that are multiples of 3 or 5

The Enumerable pattern is quite extraordinary when used in Linq like this. So I decided to use the same pattern on other problems as well.

[code lang="csharp"]
return Enumerable.Range(1, 999)
.Where(x => x % 5 == 0 || x % 3 == 0)
.Sum();
[/code]

Problem 2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million

First I made a sequence generator for Fibonacci numbers:

[code lang="csharp"]
internal static IEnumerableFibonacciSequence()
{
  long last1 = 1;
  yield return 1;

  long last2 = 2;
  yield return 2;

  while (true)
  {
    long next = last1 + last2;
    last1 = last2;
    last2 = next;
    yield return next;
  }
}
[/code]

Problem 3: What is the largest prime factor of the number 600851475143 ?

Again I start with creating a sequence generator. This one returns the sequence of factors for any number.

[code lang="csharp"]
internal static IEnumerable GetFactors(long x)
{
    for (long factor = 1; factor * factor <= x; factor++)
    {
        if (x % factor == 0)
        {
            yield return factor;
            if (factor * factor != x)
                yield return x / factor;
        }
    }
}
[/code]

We also need a small helper function to check if a number if a prime number:

[code lang="csharp"]
private static bool IsPrime(long num)
{
  long limit = (long)Math.Sqrt(num);

  for (long d = 2; d <= limit; d++)
  {
      if (num % d == 0)
          return false;
  }

  return true;
}
[/code]

Finally the actual Linq query to find the largest prime factor of the number 600851475143 :

[code lang="csharp"]
var primeFactors = from factor in GetFactors(600851475143)
                          where IsPrime(factor)
                          select factor;

return primeFactors.Max();
[/code]

I also have use the same pattern on several of the other problems like nr 10: Find the sum of all prime numbers below 2 000 000:

[code lang="csharp"]
return PrimeNumbers()
         .TakeWhile(x => x < 2000000)
         .Sum();
[/code]