《我的第一本算法书》阅读笔记 7-1 欧几里得算法

欧几里得算法（又称辗转相除法）用于计算两个数的最大公约数，被称为世界上最古老的算法。现在人们已无法确定该算法具体的提出时间，但其最早被发现记载于公元前 300 年欧几里得的著作中，因此得以命名。

在学习欧几里得算法之前，我们先来看一看数字1112和695的最大公约数是多少吧。

通常的做法是先对两个数字因式分解，找出共同的素数，然后求出最大公约数（GCD）。这样就能求出 1112和695的最大公约数为139。然而两个数字越大，因式分解就越难。此时，使用欧几里得算法就 能更高效地求解最大公约数。

那么，我们就来看一看欧几里得算法的具体操作流程吧。

首先用较小的数字去除较大的数字，求出余 数。也就是对两个数字进行 mod 运算。我们在 第5章也讲过mod运算即取余运算，A mod B 就是算出A除以B后的余数C。

除完后的余数为417。

接下来再用除数695和余数417进行mod运 算。结果为278。

继续重复同样的操作，对417和278进行mod 运算，结果为139。

对278和139进行mod运算，结果为0。也就 是说，278可以被139整除。

余数为0时，最后一次运算中的除数139就是 1112和695的最大公约数。

为什么用欧几里得算法可以求得最大公约数 呢？我们结合图片来想一想。

将最大公约数设为n，然后在直线上画出相应刻度。由于我们已知最大公约数为 139，所以为了方便理 解，在1112上画出8个刻度，在695上画出5个刻度。

这里和前面的运算一样，用小的数去除大的数，得到的余数为417。

继续重复mod运算。用417去除695，得到余数278。

继续做除法。由于278可以被 139整除，所 以……

余数为0。此时便能求得最大公约数n为139。

使用欧几里得算法，只需重复做除法便能求得最大公约数。这个算法最大的优势就 在于即使两个数字再大，只要按照步骤进行操作就能高效地求得两者的最大公约数。

《我的第一本算法书》  [日]石田保辉 宫崎修一/著    张贝/译