Euler 10

After tackling number 9 yesterday, I thought I'd do #10 real quick since it seemend pretty easy.

Calculate the sum of all the primes below two million.

The code for the algorithm was a simple 2 lines:

var range = GeneratePrimes().TakeWhile(x => x < 2000000);

int sum = range.Sum();

But I have to confess that I took most Bill's GeneratePrimes() from is solution to Euluer #7.  I say "most" because I didn't grok his implementation of IsPrime().  I read his description a number of times and even stepped through the code a couple of iterations, but I still didn't "get" his use of the List<int> to keep a list of already found primes.

So I wrote my own IsPrime().  I used the canonical definition of a prime number ("a number which is evenly divisible by one 1 and itself").

public static bool IsPrime(this int number)

{

    if (number == 1)

        return false;

    if (number == 2)

        return true;

    var range = Enumerable.Range(2, number - 2).ToList();

    return range.TrueForAll(n => number % n != 0);

}

So I started running my solution.  After about 10 minues, I paused and saw that I was still generating prime numbers in the 20,000-30,000 range.  Hmmm...  Ok, I'll just let it run overnight.

I got up about 7.5 hours after going to bed and my app was still running!  I paused it and saw it was only in the 950,000 range of determining primes below 2 million (not even half way through!).  So I decided to take 20 seconds and really THINK about my IsPrime() method and realized how inefficient it was to generate that huge range to use the 'TrueForAll' on.

So I eliminated the LINQ code and did a simple for loop that will break out as soon as it finds a number that is evenly divisible:

public static bool IsPrime(this int number)

{

    if (number == 1)

        return false;

    if (number == 2)

        return true;

    for (int n = 2; n < number; n++)

    {

        if (number % n == 0)

            return false;

    }

    return true;

}

Now I ran the code and after about 20 minutes ran into a new problem: An overflow exception calling range.Sum().  On the good side, it only took about 20 minutes to get my primes under two million.  On the bad side,  I should have thought about that line of code a little more.  Adding up all of the primes below two million is probably going to produce a huge number (much bigger than a 32-bit integer could hold).

So I decided to move the range "up" to use longs (I didn't feel like going back and changing the extension method to use longs):

var longrange = range.Cast<long>();

var sum = longrange.Sum();

Success in about 20 minutes!

PS - I went back and ripped out my IsPrime() and put Bill's back in.  Now it completes in about 5 minutes.  How come the boss is always right?