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.

可以直接遍历找出所有整除3或5的数，然后相加，需要 \(O\) (n)。但如果运用数学集合的概念,只要 \(O\) (1).

基本思路:

1. 所有被3整除数相加 3 + 6 + … + 999 = 3 * (1 + 2 + … + 333)
2. 加上所有被5整除数 5 + 10 + … + 995 = 5 * (1 + 2 + … + 199)
3. 减去被15整除的数 15 + 30 + … + 995 = 15 * (1 + 2 + …+ 16)

其中(1 + 2 + … + n) = (1 + n) * n / 2;

333 = floor(1000/3);

233168

Source:C++