# #WeHateMath Project Euler 10 – Summation of Primes

Summation of primes

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

We’ve spoken about primes before but this problem is different. First of all, it seems pretty straightforward. We’re adding up a list of numbers. Granted, we have to generate the list of numbers first but generating a list of primes is not unknown technology. (Like any nerd, I let a computer do the hard work).

The question is (as it is with all of these problems), why do it?  What’s the point? That’s what I had to ponder for a while. So I decided to let my computer grind through a few possibilities. Using a combination of a spreadsheet and some computer code (and there’s no reasonable way to do this without some programming skills), I poked at some numbers.

One of the first things I discovered was that (no surprise) the sums get big pretty quickly. I started by asking Wolfram Alpha to do prime sums for me. It worked fine for 10, 100, 1000 and up to 1000000. But when I asked for the sum of primes less than 2,000,000 it crapped out on me. You see, Wolfram Alpha has built-in limits on how much processing time you can use.

Okay, you have my interest now.

I poked around and found some program code that did sums of primes, loaded it into XCode, compiled and ran it. At first I used it to check the numbers that Wolfram Alpha had given me (no harm in checking). Of course, as the numbers got bigger, the processing took longer and longer. I decided to shorten things by asking for the sum of primes between 1,000,000 and 2,000,000 (since I already had the sum for 1,000,000). I dumped it into my spreadsheet and made a table:

 N Sum of Primes Sum of N Diff(N, Sum_of_Primes) Diff(N, Sum_of_N) 10 17.00 55.00 7.00 45.00 100 1,060.00 5,050.00 960.00 4,950.00 1000 76,127.00 500,500.00 75,127.00 499,500.00 10000 5,736,396.00 50,005,000.00 5,726,396.00 49,995,000.00 100000 454,396,537.00 5,000,050,000.00 454,296,537.00 4,999,950,000.00 200000 1,709,600,813.00 20,000,100,000.00 1,709,400,813.00 19,999,900,000.00 1000000 37,550,402,023.00 500,000,500,000.00 37,549,402,023.00 499,999,500,000.00 2000000 142,913,828,922.00 2,000,001,000,000.00 142,911,828,922.00 1,999,999,000,000.00

Just for fun, I added a column of straightforward sums plus differences. (You never know what relationships will pop up.) I also ran my prime summing program with a timer and here are the results:

`Enter min range: 2`
`Enter max range: 2000000`
`Sum of prime numbers is: 142913828922`
`real19m57.296s`
`user19m42.095s`
`sys0m0.625s`

In human-speak, this means that the calculation took almost twenty minutes of ‘real’ time (as in wall-clock time) and about two-thirds of a second of computing time. Just out of curiosity, I ran the same program but just for the primes between one million and two million:

`Enter min range: 1000000`
`Enter max range: 2000000`
`Sum of prime numbers is: 105363426899`
`real14m20.074s`
`user14m9.366s`
`sys0m0.195s`

Interestingly enough, it took almost the same amount of ‘real’ time but about a third of the computing time. Just for fun, I wondered how much time it would take to do sum of primes up to 1 million:

`Enter min range: 2`
`Enter max range: 1000000`
`Sum of prime numbers is: 37550402023`
`real5m15.445s`
`user5m7.393s`
`sys0m0.213s`

Well, about one-third of ‘real’ time and a bit more computing time. The latter was to be expected but the former isn’t.

In any event, I’m still not sure about the point to this problem. If I figure it out, I’ll post an update.