Developer Dad

I first checked out Project Euler a couple years ago when one of my friends mentioned it to me. If you haven’t heard of it before it is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve.

I took a couple classes in college for basic C++ programming, but we never got too deep. It was mostly principles of programming, etc. and, since it was a class aimed at Electrical Engineers first programming class and not Computer Science majors, we spent a bit of time on structures of programs and other general concepts that are core to most programming languages. I was (and still am) interested in strengthening my C++ knowledge, so I decided to try the Project Euler problems in C++.

So far I haven’t completed many (13 out of 228), but haven’t spent too much time on it, even though I started a couple years ago… The questions range in difficulty from Problem #1 Find the sum of all the multiples of 3 or 5 below 1000. to Problem #198 How many ambiguous numbers x = p/q, 0 x 1/100, are there whose denominator q does not exceed 10⁸? The higher number problem # doesn’t necessarily mean it is more difficult, but difficulty is measured by how many people have solved the problem. You can see a trend of how people may start doing some of the problems, but quickly the numbers dwindle. For example, over 48,000 people have completed problem #1, but less than 20,000 people have completed more than 10 and less than 2,000 people have completed more than 25 problems. Once you’ve solved a problem, you can look at other ways people have solved it in other languages or even by hand. However, you can’t see any hints or other posts about a problem on the site until you’ve typed in the correct answer for that problem.

Today I spent a little bit of time optimizing some of the old algorithms I had used for previous problems. (Several algorithms can be re-used between problems and the less time it takes for them to run, the less time you have to wait to see if your answer is correct…) I started with optimizing my function to check if a number is a prime number.

There are basic things you can do to make figuring out if a number is prime or not. For example, it’s very easy and quick to find the remainder of a number when it is divided by 2 or 3. Since this is a lot of the cases for non-prime numbers, it’s best to check these cases first before checking if a number is divisible by any other number. A couple other quick (and perhaps obvious) things to do is to not check every single number from 1 … n where n is the number you are trying to check is prime or not… We know that anything even is divisble by 2 , so instead of checking if the number is divisible by 2, 4, 6, 8… start by checking if it’s divisible by 5 (since we’ve already checked 2 and 3) and check every odd number from there (5,7,9,11…). This cuts your computations in half. Also, we know that we only have to check up to the square root of the number (16/2 = 8, so there’s no point in checking if there is a remainder with 16/8). This cuts the computations in at least half again. After adding this optimizations, my code went from a minute or two to run down to a few seconds.

If you enjoy programming, math, or especially both, I would recommend checking out some of the problems on the site. It is a great way to keep your math skills from getting too rusty and a great way to learn how to do some math programming in a new language. If nothing else, you’ll get your mind thinking of different ways to solve problems.