Project Euler Problem #1

This is the first programming challenge from Project Euler done in Java and C.  The problem is:

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.

Before tackling this problem, or any problem, we must pay careful attention to the wording and exactly what is expected of the program. We want to find the sum of all multiples of 3 or 5 below 1000.

I highlight the ‘or’ because if we were looking for multiples of 3 and 5 we would be looking for that exclusively.  Such as 15, 30, 45, 60, etc. However, with the ‘or’ we will be finding the sum of numbers like 3, 5, 6, 9, 10, etc. This of course changes the outcome entirely.

Second, we must pay careful attention to the specification “below”.  1000 is a multiple of 5 and thus would be included. Except, we want the sum of everything under 1000, or up to 999.

With this out of the way, the code becomes very simple. Because 1,000 is a low number we can use a simple for loop that goes through and checks every number from 0 to 1000 and adds them to the sum if they are multiples of 3 or 5.

Java:

C:

If we were to try and expand this to larger numbers, the program becomes inefficient. So we must find ways to improve it. Again, we should break the problem down into the basics, and break it into steps.

First, we are taking every number divisible by 3 (3, 6, 9, 12..) and adding them together. Then, we’re taking every number divisible by 5 (5, 10, 15, 20..) and adding those together. When we sum both of these answers we get something higher than we need. This is because we’ve added the numbers divisible by both 3 and 5 (or the numbers divisible by 15) twice.  So we then have to subtract those.

divisibleBy(3) + divisibleBy(5) – divisibleBy(15)

OK, so we’re on the path to a function, but this is less efficient if we’re still using a simple for loop. Let us instead go to Gauss’ formula. Gauss’ formula says that in order to find the sum of 1-100 you use the following:

(100 * (100 + 1)) / 2

-or-

(n(n+1)) / 2

To understand the formula let’s consider the sum of 1-5 rather than 100. If we list them out as such:

1 2 3 4 5

        • +

5 4 3 2 1

You might notice that the sum of every colum (1+5, 2+4,…) is 6, or 5+1 (n+1). From there we can recognize that there are 5 columns and multiply:

5(5+1)

-or-

n(n+1)

Of course, we must recognize that we’ve added every number we want twice. So we simply divide by 2.

(5(5+1)) / 2 = 15 = 1+2+3+4+5

-or-

(n(n+1))/2

Alright, but we haven’t solved our problem yet. We don’t want to add every number from 1-999, we only want to add those who are divisible by 3 or 5.

For presentations sake let’s add up all numbers divisible by 3 from 1-9.

1 2 3 4 5 6 7 8 9

9 8 7 6 5 4 3 2 1

In order to find the sum of the numbers divisible by 3 we only want to add 3, 6 and 9. But in order to represent this with our formula we first divide 9 by 3 and use our row strategy 3 times:

1 2 3 – 1 2 3 – 1 2 3

3 2 1 – 3 2 1 – 3 2 1

By adding 1 three times we get 13, or 3. We also get 23 for 6, and 3*3 for 9. Once we add everything up and divide by 2 we get our answer of 18. Our formula is:

3 * (3(3+1)) / 2

-or-

x * (n(n+1) / 2, where x = our target / n

And so we finally get to our code:

Java:

C:

Back to Top

Back to top ▴