Project Euler, Problems 11 Through... Lots

Saturday, June 4, 2011
Tags: project euler, cplusplus, code sample

My last few posts were about the solutions I've been writing for the problems from Project Euler. There are a lot of problems, and commentary on the individual solutions aren't all that interesting.

Therefore, instead of posting solutions here I've started pushing them to a GitHub repository. At the time of writing, I've solved the first 45 problems.

A few of the problems offered opportunities to use dynamic programming, which is a technique I haven't encountered much since leaving college. I was glad to have a chance to use it again, and refresh my memory. The result tends to be a very fast solution.

Some problems require very large integers, and in some cases I'm using the long long type which isn't officially part of C++. However, even this isn't big enough for some problems. In a few cases I "faked" arbitrary precision integers, then at problem 20 I started to implement a separate BigInt class, but only having the parts I needed for that problem. I quickly decided that it would be more useful to use a common arbitrary precision library, and switched to using GMP for later problems that required very large integers. Reinventing the wheel isn't really the point of the problems, after all.

I eventually added a utility module for things that I've been using over and over again, such as a primality testing function. There are still many copies of this function in the earlier problems because I didn't bother to update them. Once I have the solution, I consider the program complete.