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.
This is the first "easy" problem, still has some remarkable points worth thinking.
1) a simple brute-force solution:
Iteration through all the integers <1000
2) a better approach :
Get the multiples of 3, the multiples of 5, and remove the common items ( the multiples of 15)
3) but wait, we don't need the exact entries. Is there a faster way if we just want the quantity?
* Multiples of 3 below 1000 = 3+6+9+12+......+999=3*(1+2+3+4+...+333) = 3*(1+2+...+⌊999/3⌋)
* Multiples of 5 below 1000 = 5+10+15+...+995=5*(1+2+....+199) = 5* (1+2+...+⌊999/5⌋)
And notice that 1+2+3+...+p=½*p*(p+1)
So, the solution just need to do a simple math:
3*(½*⌊999/3⌋*(⌊999/3⌋+1)) + 5*(½*⌊999/5⌋*(⌊999/5⌋+1)) - 15*(½*⌊999/15⌋*(⌊999/15⌋+1))
P.S. Debug notice: notice the number used in the floor fn is 999, not 1000.
[GitHub Link] [Official overview pdf by projecteuler.net]
1) a simple brute-force solution:
Iteration through all the integers <1000
2) a better approach :
Get the multiples of 3, the multiples of 5, and remove the common items ( the multiples of 15)
3) but wait, we don't need the exact entries. Is there a faster way if we just want the quantity?
* Multiples of 3 below 1000 = 3+6+9+12+......+999=3*(1+2+3+4+...+333) = 3*(1+2+...+⌊999/3⌋)
* Multiples of 5 below 1000 = 5+10+15+...+995=5*(1+2+....+199) = 5* (1+2+...+⌊999/5⌋)
And notice that 1+2+3+...+p=½*p*(p+1)
So, the solution just need to do a simple math:
3*(½*⌊999/3⌋*(⌊999/3⌋+1)) + 5*(½*⌊999/5⌋*(⌊999/5⌋+1)) - 15*(½*⌊999/15⌋*(⌊999/15⌋+1))
P.S. Debug notice: notice the number used in the floor fn is 999, not 1000.
[GitHub Link] [Official overview pdf by projecteuler.net]