Problem #1 of Project Euler reads:

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.

Here's my attempt:

```
T = int(input())
for i in range(T):
sum = 0
a = int(input())
for j in range(a):
if (j%3==0 or j%5==0):
sum = sum + j
print(sum)
```

The code above raises an time complexity i.e., for some cases run for >10. you can find details here:

## Answer

You can calculate the sum of all natural numbers that are multiples of `n`

and are below `m`

as a trapezoidal area:

```
def sum_multiples(n, m):
d = (m - 1) // n
return (1 + d) * d // 2 * n
```

so that the sum of all the multiples of 3 or 5 below `m`

can be calculated in a time complexity of *O(1)* by calculating the sum of all the multiples of 3 plus the sum of all the multiples of 5 minus the sum of all the multiples of 15, the lowest common denominator of 3 and 5:

```
def sum_3_5(m):
return sum_multiples(3, m) + sum_multiples(5, m) - sum_multiples(15, m)
```

So to answer the question, `sum_3_5(1000)`

returns:

```
233168
```