ruby - 欧拉计划 1 :Find the sum of all the multiples of 3 or 5 below 1000

Question

我正在尝试使用 Project Euler 中的 Ruby 解决数学问题。 Here是我尝试的第一个:

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

Answer 1

更快(恒定时间)答案:

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

为什么会这样？ sum_multiples 计算 multiple 的倍数之和，直到但不包括 to(它依赖于整数除法)。它首先计算求和的倍数 (n)，然后将 1..n = n(n+1)/2 之和的标准公式乘以 multiple 。使用它，我们可以将 3 和 5 的倍数的总和加在一起。然后我们一定不要忘记有些数字是 3 和 5 的倍数，所以我们减去 15 的倍数 (3*5 ).

虽然您的答案对于这个问题的约束来说已经足够快了(在现代硬件上它应该在大约 1 毫秒内运行)，但更快的解决方案(例如我提供的解决方案)将给出非常大的数字的结果。