Code Kata – Euler Project 1 in C#

Euler-Project-1

Today I thought I’d write about some programming that I’ve been playing around with by using the famous Euler Projects.

Project Euler is a list of mathematical problems which can be solved using computer programs. They range from fairly simple through to very complex and can tend to be a bit too mathematical for my liking. If you haven’t heard of it before I highly recommend you go check it out.

I’m planning to use these projects as “practice” programming. Experts in almost every field will have a way to practice or train their skills other than actually completing the entire task. The classic analogy is in sports. Professional athletes don’t just practice by playing an entire game. Instead they break down the game into defined skills and then practice these skills individually so they can dedicate their focus to this particular area of the game. Through this highly focused effort they are able to achieve better results than just working through an entire game. So if we want to be expert programmers why not follow the same principle?

In fact a lot of other development experts have suggested this over the years and the exercises suggested have come to be called “code katas” after the karate exercise where a move is repeated over and over until perfected. Obviously the Euler Projects aren’t the only code katas out there. Some other good resources include:

I’ll also be working through these in future posts. But for today lets get started on the first Euler Project.

Euler Project 1 – Multiples of 3 and 5

The outline for the first Euler Project is as follows:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

There are a couple of ways we could solve this. We could use the brute force approach and simply iterate over each number checking if it is a multiple of 3 or 5. That would work fine in this case because we are only checking numbers below 1000. In fact you could do this by hand in a few minutes! But what happens if we need to check numbers up to 1 million or 1 billion? It quickly starts to slow down. That is because of the number of iterations we need to complete. The complexity of the brute force solution is O(N) so the time it takes to get to answer is proportional to the amount of numbers we need to check. Can we think of a better way?

The solution I ended up with is certainly more an algorithmic solution rather than a pure math solution. For a more efficient but more maths focused solution see the MathBlog post on the topic. Anyway, here is what I ended up doing:

As you can see we use a single function to calculate the sum of the multiples of a given divisor up to the max. In this case we use the divisors of 3 and 5 and a max value of 1000.

Also note that we need to subtract the sum of multiples of 15 as they will be counted twice, once by the function call with 3 and again with the call for 5.

We mentioned before about efficiency and complexity. This algorithm is still O(N) complexity but is slightly better than the brute force approach as the for loop in the CalculateSumOfMultiples fuction steps ahead by the divisor. So instead of checking every number it only sums those numbers which match the divisor we are looking for. Again see the MathBlog post for a more mathematical solution.

Summary

So there you have it. A nice simple exercise you can use to practice your coding and algorithm skills. This project can easily be completed in any number of different languages so it would be a nice way to test out your skills in a language you are learning.

You can find the complete source code on GitHub at https://github.com/gabeb1920/EulerProject1C-.git

Did you find this useful? Please let me know in the comments what you think of these style of articles as well as what technical articles you’d like to see in the future.

Leave a Reply

Your email address will not be published. Required fields are marked *