I’ve been working my way through Project Euler recently, and I’ve decided to start posting my solutions with their explanations. So far I’ve been solving everything in C++, but for these posts I’m going to translate into Python, too. Because masochism.

Project Euler #1: Multiples of 3 and 5

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.

Being the first, this one is pretty dead simple. My first solution was just the most obvious thing to do: count up from 0 to 999, check for multiples of 3 and 5 along the way, and add them up as I find them:

include <iostream>
using namespace std;

int main()
{
     int answer = 0;
     for (int i = 0; i < 1000; i++){
          if ((i%3 == 0) || (i%5 == 0)) {answer += i;}
     }
     cout << endl << "The sum of all natural multiples (remainder method) of 3 and 5 between 0 and 1000 is " << answer << endl;
     return 0;
}

Same solution in Python:

answer = 0
for i in range(0, 1000):
     if (i%3==0) or (i%5==0):
          answer += i
print "The sum of all natural multiples (remainder method) of 3 and 5 between 0 and 1000 is " + str(answer) + "."

This solution works, but I couldn’t help but think it wasn’t very efficient. We’re counting and checking every single integer from 0 to 999, when we could be incrementing by multiples, instead. Of course, with such a small range, it hardly matters – the programs both complete in the blink of an i (get it? Ha!). But if we ever wanted to increase the range, efficiency might start to matter. So I wanted to do better. That led me to this solution (in Python):

threes = 0
fives = 0

i = 3
while i < 1000:
    threes += i
    i += 3

i = 5
while i < 1000:
    if i%3 != 0:
        fives += i
    i += 5
    
print "The sum of all natural multiples (multiple method) of 3 and 5 between 0 and 1000 is " + str(fives+threes) + "."

The code looks much less elegant, but this solution should take approximately half the number of steps as the first, making it preferable for larger ranges. Instead of checking every digit from 0 to 999 to see if they happen to be multiples of 3 or 5, this solution starts at 3, then increments by 3 all the way to 999, adding up all the increments along the way. Then it repeats by 5’s, while also checking to make sure it doesn’t add any digit that is a multiple of BOTH 3 and 5 (ie, {15, 30, 45 … 990}), because those were already included in the 3’s.

The code is uglier, but faster. I hate when that happens.

Advertisements