ruby - 这个解决方案的数学逻辑是什么(找到一个数字是数字 1 到 20 的倍数)

Question

2520 是 1 到 10 中每一个数都可以整除而没有余数的最小数。

能被 1 到 20 的所有数字整除的最小正数是多少？

我已经找到了解决方案，但它几乎是暴力破解，大约需要 7 秒才能找到解决方案。

我在 stackoverflow 上找到了答案，但无法理解找到答案背后的逻辑。我知道 LCM 和 GCM 是什么，但他是如何想出以这种方式使用它们来找到答案的？ (即 232,792,560)

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

Answer 1

更短的方法，使用 Integer 的内置 lcm 方法

p (2..20).inject(&:lcm)  # => 232792560

“lcm”表示“最小公倍数”。 (复习一下:lcm 在加减不同分母的分数时很有用)。上面的代码是对以下过程进行编码的一种极其简洁的方式:

• 取2和3，计算lcm，为6。
• 用这 6，计算下一个数字 4 的 lcm。结果是 12。
• 计算lcm12 和 5。结果 60
• 计算60和6的lcm，结果60
• 等一直到 20