Bill Blogs in C#

Euler Problem 10

Patrick posted his solution earlier this week. I figure it was time to add mine.

Also, Octavio Hernandez pointed out in the comments to problem 8 that he had discussed similar code constructs in his blog a while back.

Problem 10 asks for the sum of all primes less than 2 million. It's also one line of LINQ code:

   1: var number = Common.Primes.GeneraePrimes().TakeWhile((n) => n < 2000000).Sum();

   2: Console.WriteLine(number);

As Patrick pointed out, this will cause an overflow unless you make some changes to the GeneratePrimes() method so that it returns a sequence of longs instead of a sequence of ints.

I also wasn't thrilled with the fact that it was taking a few minutes to finish instead of seconds.  That needed some fixing.

George Byrkit pointed out that the math can be optimized by recognizing that the highest factor you need to check for any N is Sqrt(N).

Sadly, the current .NET Framework does not contain methods that do the check efficiently. George suggested using List<T>FindAll() to find only those numbers smaller than the target. That method is a member of List and creates a new List object. Yuck. Also, it doesn't perform lazy evaluation, and it checks the entire list.

But now that the numbers have gotten much larger, it's worth the work to create my own version of those methods that speed this up.

Here's the new version of IsPrime:

   1: public static IEnumerable<long> GeneratePrimes()

   2: {

   3:     var range = Enumerable.Range(2, int.MaxValue-1);

   4:     var answers = from number in range

   5:                   where number.IsPrime()

   6:                   select (long)number;

   7:  

   8:     return answers;

   9: }

The only change here is to cast the prime number to a long before returning.

IsPrime gets a slightly larger makeover:

   1: private static bool IsPrime(this int number)

   2: {

   3:     bool isPrime = knownPrimes.TakeWhile(n => n*n <= number).

   4:         TrueForAll(n => number % n != 0);                   

   5:     if (isPrime)

   6:         knownPrimes.Add(number);

   7:     return isPrime;

   8: }

The astute reader will immediately notice that I'm calling TrueForAll using an IEnumerable<int> instead of a List<int>. That's not supposed to compile. And in fact, it doesn't, until I write my own version of TrueForAll:

   1: public static bool TrueForAll<T>(this IEnumerable<T> sequence, Predicate<T> test)

   2: {

   3:     foreach (T item in sequence)

   4:         if (!test(item))

   5:             return false;

   6:     return true;

   7: }

Note that this is typed for IEnumerable<T>, so the compiler will use this version on sequences that are not List<T>, but will still use the base framework version for all List<T> types.

And, now it produces the correct answers in under a minute.