项目Euler 1:找到1000或以下3或5的所有倍数的总和

Question

我试图用Project Euler解决Ruby中的数学问题.这是我尝试过的第一个:

如果我们列出10以下的所有自然数是3或5的倍数,我们得到3,5,6和9.这些倍数的总和是23.

求出1000以下3或5的所有倍数的总和.

请帮我改进我的代码.

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毫秒),但是更快的解决方案,例如我提供的解决方案,会产生非常大的数字.