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

Project Euler’s first problem:

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.

By brute force I can write code that checks every number below 1000 to see if it’s divisible by 3 or 5, if it is then add it to a running total.

I’m using Visual Basic (VB.Net 2010 to be precise). This might seem a little odd for an Ubuntu member but I’m thinking of trying MT264 (Designing applications with Visual Basic). Open University students qualify for Microsoft’s Dreamspark promotion, so I got a copy of Visual Studio 2010 Express to try it out. Besides, I’m at work so haven’t much choice.

Starting off with a “Console Application” template:

Dim beganAt As Date = Now
Dim total As Long = 0
' Repeat a thousand times
For counter As Integer = 1 To 999 Step 1
     ' Check if the current integer is divisible by 3 or 5 and
     ' if it is then add it to our total
     If (counter Mod 3 = 0) Or (counter Mod 5 = 0) Then
          total = total + counter
     End If
Next
Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
Dim took As Integer = endAt.Milliseconds
Console.WriteLine(total.ToString + " in " + took.ToString + "ms.")
Console.ReadKey()

Running this code and clicking the button we get the answer 233168, which Project Eular confirms. Code must run in less than a minute, the timer shows less than a millisecond.

I can see another way to do this, by using two for loops – one in steps of 3 and one in steps of 5, adding the counter to a total for each. I don’t know if this offers a significant time saving, so I re-ran the original code, making the loop repeat a million times and it completes in 375ms. I can’t see any value in going any further.

2 thoughts on “Find the sum of all the multiples of 3 or 5 below 1000”

  1. if you choose to create two separate loops there is one pitfall you have to watch out for: take for example the number 15. It is divisible by both 3 and 5. for that reason it will be included in both loops which means your result will have duplicate numbers added to it like 15; 30; 45; … The way to avoid this while still using two loops makes the whole method longer. And so one loop that checks both at the same time is the best 🙂

Comments are closed.