[ProjectEuler] 1. Multiples of 3 or 5
Find the sum of all natural numbers below 1000 that are multiples of 3 or 5.
Solution
Sum of multiples of 3 + sum of multiples of 5. Since multiples of 15 are counted twice, subtract them once.
Step 1: Count of each multiple
999 / 3 = 333 -> 333 multiples of 3
999 / 5 = 199.8 -> 199 multiples of 5
999 / 15 = 66.6 -> 66 multiples of 15
Step 2: Apply arithmetic series formula
1 + 2 + ... + n = n(n + 1) / 2
(1 + 2 + ... + 333) = 333 * 334 / 2 = 55611
(1 + 2 + ... + 199) = 199 * 200 / 2 = 19900
(1 + 2 + ... + 66) = 66 * 67 / 2 = 2211
Step 3: Calculate sum of each multiple
3 * (1 + ... + 333) = 3 * 55611 = 166833
5 * (1 + ... + 199) = 5 * 19900 = 99500
15 * (1 + ... + 66) = 15 * 2211 = 33165
Step 4: Final sum
sum = 166833 + 99500 - 33165 = 233168
(Multiples of 15 are counted twice because they are both multiples of 3 and 5, so we subtract them once.)