缓慢的Ruby计算？欧拉项目#5

Question

这个问题参考了欧拉项目问题5，所以要小心剧透！问题5：

2520是可以被1到10的每个数字除的最小数，没有任何余数。可以被1到20的所有数字整除的最小正数是多少？

我用Ruby编写了以下代码作为问题5的解决方案。

num = 2520
until (1..20).all?{|x| num % x == 0}
  num += 1
end
puts "#{num}"        

然而，每当我运行脚本时，它都会挂起。请注意，我在1到10范围内的基本情况2520上测试了相同的方法，效果很好。

为什么它适用于更简单的情况，但不适用于更高级的情况？我能做些什么来修复我所拥有的？

Answer 1

比赛有点晚了，但这是我的意见。如果你喜欢简洁明了的代码，你可以做一些小的调整，让它运行得更快。这在没有超时的情况下对我有效：

num = 20

  until (11..20).all?{ |i| num % i == 0 }
    num +=20
  end

puts num

本质上，你只需要增加20秒，因为你知道它需要被20整除，你可以跳过迭代通过集合的低1/2的任何东西。

Answer 2

你不能像对待别人那样粗暴地对待这个问题。你需要找到一个更有效的解决方案。

这是一种更有效的方法（如果这不是很像Ruby，请道歉）：

def find_multiple
  lcm = 1

  (2..20).each do |i|
    lcm *= i / gcd(lcm, i)
  end

  lcm
end

def gcd(a, b)
  while b > 0
    a %= b
    return b if a == 0
    b %= a
  end

  a
end

puts find_multiple

如果您正在寻找一种更像Ruby的方法来解决这个问题，您可以使用以下方法（正如steenslag在评论中建议的那样）：

(1..20).inject(:lcm)

Answer 3

它很慢，因为答案不止2亿，而且你要按1的步骤计数。这需要一段时间。你需要一个更好的算法。