Wednesday, 4 March 2009

Project Euler, Problems 10 and 17

Problem 10
Calculate the sum of all the primes below two million.

I was thinking about this for quite a while; it's extremely simple to write something which checks if a number is prime or not, and it's just as simple to put together a loop to check all of the primes below two million (start with 3, go for all the odd numbers up to 1999999, add the contribution of 2 at the end). The problem is actually summing all of that, because the basic C++ construction can't handle it with simple integers (which is pretty much all I can do at the minute!).

Then, late last night I had my idea: check what the limit is for integers, and then have it sum up to somewhere just below that limit, then output the sum and start from 0 and keep going, summing and outputting all the way up to two million. This gave somewhere in the region of seventy 10-digit numbers. Ouch! Except I could then copy the output, import it into OpenOffice Calc and get that to sum them all. Problem solved.

Problem 17
If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total. If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

For a little while I thought - for some reason, I don't know - that this was much more difficult than it actually is. It's quite easy. Work out the number of letters used to write the numbers one to nine, and then ten to nineteen. Now, for twenty to twenty-nine the total letters are going to be 6*10 (for all of the "twenty"s) plus the total letters for writing the numbers one to nine. Repeat for thirty through to ninety-nine, take the total and you have the number of letters for one through to ninety-nine.

Then, for example, from one hundred to one hundred and ninety nine we have 100*10 (for all of the "one hundred"s) plus 99*3 (for all of the "and"s) plus the total letters for one to ninety-nine. Repeat for all of the other hundreds, and add 11 at the end for "one thousand". I thought this was so much more difficult than it was, but after the idea came to me it took me about twenty minutes with pencil and two small pieces of notepaper, all worked out by hand.


And that my friends, is twenty-five problems done for Project Euler. Blog post on completing Thing 82 to follow!

No comments: