整除和素数最小公倍数

两个跑步者正在环形跑道上训练。第一个跑步者__跑一圈需要{.m-blue}60__ 秒，第二个跑步者__跑一圈需要{.m-blue}40__秒。如果两人同时从起跑线 上出发，他们什么时候会在起跑线上再次相遇？

这个问题实际上不是关于赛道的几何学，也不是关于速度和快慢的，而是关于倍数和整 除的。

第一个选手在60秒、120秒、180秒、240秒等后穿过起跑线，这些只是__60__的倍数因子。 第二个选手在40秒、80秒、120秒、160秒等后穿过起跑线。两位选手同时第一次回到起 跑线上是在秒之后。

我们找到的是个同时是__{.m-green}40__ 和__{.m-blue}60__ 倍数的最小数，这也被称为__最小公倍数__或缩写为__lcm__.

求任意两个数__{.m-yellow}a__和__{.m-blue}b__最小公倍数，如果__{.m-yellow}a__ 整除 b, 那么很重要的一点是要认识到__{.m-blue}b__必须具有__{.m-yellow}a__ 的所有素数因子(外加其它的):

这很容易验证：如果一个素数因子整除__{.m-yellow}a__，同时__{.m-yellow}a__整除 b，那么该素数因子一定__也__整除__{.m-green}b__。

为了找到__{.m-green}40__和__{.m-blue}60__的最小公倍数, 我们首先数需要找到两者 的共有素数因子:

假设__{.m-red}X__是__{.m-green}40__和__{.m-blue}60__的最小公倍数。那么 40__整除{.m-red}X__，所以_{span.number-ball.small.l-blue}2_， 2，2_和 5_必定是{.m-red}X__的素数因子。同理， 60__整除{.m-red}X__，所以_{span.number-ball.small.l-green}2_, 2,和_{span.number-ball.small.l-green}3_ 和_{span.number-ball.small.l-green}5_必定是__{.m-red}X__的素数因子。

要找到__{.m-red}X__，我们只需将__{.m-green}40__和__{.m-blue}60__的所有素数因子 组合在一起，但是两边出现相同因子时我们只需要一份：

X  =  2 × 2 × 2 × 3 × 5

我们从这得到__{.m-red}X__ = 120，就像我们看到的上图。注意，如果相同的素数因子出 现多次，如上面的2，我们需要保持两个次数中最大的那个次数(40__中的 3次比{.m-blue}60__中的2次多）。

现在我们有了一个简单的方法来查找两个数字的最小公倍数：

1. 找出每个数的素数因子。
2. 将所有数素因子组合起来，但重复出现的只算一次。

我们可以使用相同的方法找到三个或更多数的最小公倍数，如__{.m-blue}12__、 30__和{.m-yellow}45__：

因此__{.m-blue}12__, 30 和 __{.m-yellow}45__的最小公倍数是 2 × × 3 × 3 × = 180.

一个特例是质数：两个不同质数的最小公倍数是它们简单的求积和差, 因为它们没 有任何共同的数素因子会被“消去”。

蝉

13和17都是质数 - 这是有充分理由的。想象一下森林里有捕食者杀死了蝉。这些捕食者 也会定期出现，比如每6年出现一次。

现在想象下蝉的出现间隔是每${n}年(${isPrime(n) ? '素数' : '非素数'})。 这两种动物每${lcm(n,6)}年会相遇一次，这就是6和${n}的最小公倍数最大公约数乘积

如果蝉的间隔周期是像13和17这样的质数，这个数字看起来就要大得多。这是因为素数 不与6共有任何因子，所以在计算最小公倍数时，我们不会消去任何重复因子。

当然，蝉不知道素数是什么，但在数百万年的时间里，进化证明了素数周期是最安全的。 捕食者似乎已经随着时间的推移而灭绝，但素数周期仍然存在。