Project Euler #1 - Multiples of 3 or 5
My solution to Project Euler problem #1, "Multiples of 3 or 5."
author: Max Niederman, published: 2022-03-20
The first Project Euler problem reads as follows:
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.
Trivial Solution
The simplest solution is to just iterate over all numbers from 0 to 1000, check if they are multiples of 3 or 5, and sum those that are.
let sum = 0;
for i in 0..1000 {
if i % 3 == 0 || i % 5 == 0 {
sum += i;
}
}
or in a more functional style:
let sum = (0..1000).filter(|i| i % 3 == 0 || i % 5 == 0).sum();
This has a runtime complexity of
Constant-Time Solution
The crucial insight which allows us to solve the problem in constant time is the fact that the sum is equal to the sum of the multiples of 3 plus the sum of the multiples of 5 minus the sum of multiples of both (i.e. multiples of 15).
We can then use the formula for the sum of the first
Now we simply substitute the numbers given by the problem:
This gives us our final answer of