Skip to content

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.

Solution

It is possible to fund the sum of all multiples of nn below mm using a formula.

To find the sum of all multiples of nn below mm, the individual multiples have to be summed up.

1∗n+2∗n+3∗n+…x∗n 1 * n + 2 * n + 3 * n + \dots x * n

Here, x∗nx * n is the largest multiple that is lower than mm, so it can be said that

x=⌊x−1n⌋ x = \left \lfloor\frac{x - 1}{n}\right \rfloor

This can be rearranged such.

(1+2+3+…x)∗n (1 + 2 + 3 + \dots x) * n

The Gaußian sum formula can be used to simplify this.

n∗x2+x2 n * \frac{x^2 + x}{2}

C

uint32_t sum_divisible(uint32_t max, uint32_t divisor) {
  // smallest number lower than max that is
  // divisible by divisor
  int bound = max - (max % divisor);

  return (bound * ((bound / divisor) + 1)) / 2;
}

uint32_t sum_multiples(uint32_t max, uint32_t div1, uint32_t div2) {
  return sum_divisible(max, div1) + sum_divisible(max, div2) -
         sum_divisible(max, lcm(div1, div2));
}