## 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();`