Problem 001


Project Euler

Multiples of 3 and 5

Problem 1

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.


With modern computer, the brute force approach would be easy enough by looping from 3 to 999 and add the number to the sum when it is divisible by 3 or 5. This will give us O(n) complexity. However, if you know a little bit about set theory:

|P \cup Q| = |P| + |Q| - |P \cap Q|

and a little bit about summation:

\sum_{i=1}^n i = 1 + 2 + 3 + \ldots + n = \frac{(n)(n+1)}{2}

\sum c \cdot i = c \sum i

Then, this problem is an O(1) complexity by calculating the sum of multiple of 3, 5 and 15 using the summation formula and subtract the sum of multiple of 15 from the sum of multiple of 3 and 5.

Advertisements