词汇表

选择左侧的一个关键字...

整除和素数最小公倍数

阅读时间: ~10 min

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

START 40 80 120 60 120

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

第一个选手在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__ 的所有素数因子(外加其它的):

12
60
2
 × 
2
 × 
3
2
 × 
2
 × 
3
 × 
5

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

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

40
=
2
×
2
×
2
×
5
60
=
2
×
2
×
3
×
5

假设__{.m-red}X__是__{.m-green}40__和__{.m-blue}60__的最小公倍数。那么 40__整除{.m-red}X__,所以_{span.number-ball.small.l-blue}2_, 2_,{span.number-ball.small.l-blue}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__:

12
=
2
×
2
×
3
30
=
2
×
3
×
5
45
=
3
×
3
×
5

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

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

北美是各种各样的蝉群的家园。这些蝉有一种奇特的特性,即它们每隔多年的夏季才出 来繁殖——剩余时间它们在地下度过。

例如,佛罗里达州和密西西比州的蝉每13年出现一次。伊利诺斯州和爱荷华州的蝉只每 17年出现一次。但是没有一种蝉有12年、14年、15年或16年的出现周期。

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

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

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

不同的蝉出现周期长度, 决定了蝉和捕食者相遇的时间。

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

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

Archie