bees - 3 months ago 7x

Ruby Question

I am trying to solve math problems with Ruby from the Project Euler. Here is the first one I tried:

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.

Please help me to improve my code.

`total = 0`

(0...1000).each do |i|

total += i if (i%3 == 0 || i%5 == 0)

end

puts total

Answer

Much faster (constant time) answer:

```
def sum_multiples(multiple, to)
n = (to-1) / multiple
n * (n+1) / 2 * multiple
end
irb(main):001:0> sum_multiples(3, 10) + sum_multiples(5, 10) - sum_multiples(15, 10)
=> 23
irb(main):002:0> sum_multiples(3, 1000) + sum_multiples(5, 1000) - sum_multiples(15, 1000)
=> 233168
```

Why does this work? `sum_multiples`

works out the sum of multiples of `multiple`

up to but not including `to`

(it relies on integer division). It first works out the number of number of multiples being summed (`n`

), then multiples the standard formula for the sum of 1..n = n(n+1)/2 by `multiple`

. Using this, we can add together the sums for the multiples of 3 and 5. We must then not forget that some numbers are multiples of *both* 3 and 5, so we subtract multiples of 15 (3*5).

Although your answer is more than fast enough for the constraints in this problem (it should run in about 1 millisecond on modern hardware), a faster solution such as the one I provide will give a result on very large numbers.

Source (Stackoverflow)

Comments