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)
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,