Happy new year everyone! Hope you had a great holiday. As a new hope for this year I wanted to improve my problem solving ability and also to improve my programming skill. So I am doing 100 days of code challenge. I will be using Python 3 programming language to solve the coding challenges.
In this post, I am going to solve Project Euler’s 1st problem.
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.
def calculate_sum_of_multiples(start, end, divisible_by_list): sum_of_multiples = 0 for num in range(start, end): if any(num % div == 0 for div in divisible_by_list): sum_of_multiples += num return sum_of_multiples start = 1 end = 1000 divisible_by = [3, 5] total_sum = calculate_sum_of_multiples(start, end, divisible_by) print("Sum of multiples between %s and %s that are divisible by %s is %s" % (start, end, divisible_by, total_sum))
While this code works and logically correct, there is a performance issue with this approach. This code will run slow if we increase the range to a huge number.
Let’s solve this mathematically, To find the sum of natural numbers up to the end that are divisible by n. p = end / n sum of multiples = ( n * (p * (p+1)) ) / 2
Note that division result is rounded off to nearest integer. And the other thing is when we are calculating sum of multiples of 3 and 5 separately, the multiples of 15 are also summed which are duplicates of 3 and 5 and it results in wrong result, To fix it we can subtract the sum of multiples of 15.
start = 1 end = 999 divisible_by = [3, 5] def calculate_sum_of_multiples(n): p = int(end/n) sum_of_multiples = (n * (p * (p+1)))/2 return int(sum_of_multiples) total_sum = calculate_sum_of_multiples(3) + calculate_sum_of_multiples(5) - calculate_sum_of_multiples(end, 15) print("Sum of multiples between %s and %s that are divisible by %s is %s" % (start, end , divisible_by, total_sum))