Sum Multiples
We are given a positive integer ( n ), and we want to find the sum of all integers in the range ( [1, n] ) that are divisible by 3, 5, or 7. We can accomplish this by using a mathematical formula that makes use of the principle of inclusionexclusion.
Approach
Calculate Sum for Each Divisor: We need to find the sum of numbers divisible by 3, 5, and 7. We can do this by using the formula for the sum of the first ( k ) multiples of ( d ): [ \text{sum}(d, k) = d \times \frac{k \times (k + 1)}{2} ] Here, ( d ) is the divisor (3, 5, or 7), and ( k ) is the number of times ( d ) divides ( n ) (i.e., ( k = \left\lfloor \frac{n}{d} \right\rfloor )).
Apply InclusionExclusion Principle: To avoid counting numbers that are divisible by more than one of the divisors (3, 5, 7), we need to subtract the sum of numbers divisible by the least common multiples (LCM) of these divisors.
Calculate Final Result: Sum the results from step 1 and then subtract the results from step 2.
Code
Here’s the Python code implementing the above approach:


Example
 For
n = 7
, the function returns 21.  For
n = 10
, the function returns 40.
Complexity
The code executes in ( O(1) ) time, as it involves basic arithmetic operations, and uses ( O(1) ) extra space. This approach efficiently calculates the sum of numbers in the given range satisfying the constraint.