This code is extremely inefficient. Using some basic math we can reduce runtime to constant time complexity. For any n
(in this case 1000), we can predict the number of numbers < n
and divisible by 3 or 5:
- numbers divisible by 3: lowerbound(n / 3)
- numbers divisible by 5: lowerbound(n / 5)
The sum of all numbers divisible by 3 or 5 can then be predicted using eulers formula:
the sum of all numbers from 1 to n
is n(n + 1)/2
. Thus the sum of all numbers n
divisible by 3 is:
int div_3 = (n / 3)
int sum_div_3 = div_3 * (div_3 + 1) / 2 * 3
Now there's only one point left: all numbers that are divisible by 3 and 5 appear twice in the sum (in the sum of all numbers divisible by 3 and the sum of all numbers divisble by 5). Since 3 and 5 are prim, all numbers that are divisible by 3 and 5 are multiples of 15.
int sum_div3_5(int n)
int div_3 = (n - 1) / 3 ,
div_5 = (n - 1) / 5 ,
div_15 = (n - 1) / 15
int sum = div_3 * (div_3 + 1) * 3 / 2 + //sum of all numbers divisible by 3
div_5 * (div_5 + 1) * 5 / 2 - //sum of all numbers divisible by 5
div_15 * (div_15 + 1) * 15 / 2
return sum
I can't provide python code though.