bees - 1 year ago 81
Ruby Question

# Project Euler 1:Find the sum of all the multiples of 3 or 5 below 1000

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.

``````total = 0

(0...1000).each do |i|
total += i if (i%3 == 0 || i%5 == 0)
end

puts total
``````

``````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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download