Problem 1 - Multiples of 3 or 5

If we list all the natural numbers below \(10\) that are multiples of \(3\) or \(5\), we get \(3,\hspace{2mm} 5,\hspace{2mm} 6\) and \(9\). The sum of these multiples is \(23\).

Find the sum of all the multiples of \(3\) or \(5\) below \(1000\)

This question seems easy to understand at a glance (and it really is) with the example given, that for every number from \(0\) to \(10\), we check that can it be divided by \(3\), or \(5\)

This is achieved with line number 5 below, and finally tally up the sum with sum_number:

def calculate_sum(limit):
  sum_counter = 0

  for x in range(limit):
    if x % 3 == 0 or x % 5 == 0:
      sum_counter += x
  
  return sum_counter

This is good! But, can we further optimize it?

Optimization

Turns out that since the question asked for multiples of \(3\) and \(5\), we can generate a sequence of \(3\)’s and \(5\)’s, up until it reaches the limit that we passed in. Here, we are using set data structure provided by Python, as it will only push unique elements to the set without duplication to avoid double counting.

def calculate_sum_v2(limit):
  multiples = set(list(range(3, limit, 3)))
  multiples.update(list(range(5, limit, 5)))

  return sum(multiples)

This is evident with the output below with input \(300,000,000\) on both algorithms.

Input: 300000000
Sum: 20999999850000000
--- 19.423505783081055 seconds ---

Input: 300000000
Sum: 20999999850000000
--- 12.689831733703613 seconds ---