数论算法编程之欧几里得算法求最大公约数和最小公倍数

从本文开始讲将一些数论算法理论知识，以及具体题目，帮助更多学习算法的同学掌握数论算法知识。本文主要讲一些数论的基础和欧几里得算法，并通过欧几里得算法求最大公约数和最小公倍数。

一. 基础知识

在开始之前，我们先来了解一些数论基础知识。由于数论是研究的整数之间的规律，先来看看整除的定义

如果整数a除以非零整数b，商为整数，余数为零，我们就说a能被b整除，或者b能整除a，记作b|a，那么a叫做b的倍数，b叫做a的约数或因数。

假如整数a除以非零整数b的余数为r，那么r=a mod b，数论中用mod表示取余。

假如d是整数a和整数b的公约数，那么有d|a和d|b，即整数a和b都能被d整除，其中满足条件最大的d叫做a和b的最大公约数，记作d=gcd(a, b)。

假如c是整数a和整数b的公倍数，那么有a|c和b|c，即整数c都能被整数a和b整除，其中满足条件最小的c叫做a和b的最小公倍数，记作c=lcm(a, b)。

二. 欧几里得算法

欧几里得算法又叫做辗转相除法，它是用来求最大公约数的，最小公倍数也可以通过它间接求出。

先来看欧几里得算法的原理，假如a>b，且r=a mod b，那么a = k*b+r，假如d是a和b的公约数，即满足d|a和d|b，r可以表示为r=a-k*b，因为a和b能被d整除，那么r也能被d整除，即d|r，所以d也是b和r的公约数，那么d为最大公约数也是满足这个条件的，所以有如下结论

上式就是一次辗转相除了，由于余数r是逐渐减小的，到某一时刻它会为零，即

很明显这里的m就是a和b的最大公约数了，其它公约数也一定是m的因数。我们来举一个实例看一下这个过程，比如求21和15的最大公约数

上述就是辗转相除的过程，具体表示为

所以最终算出21和15的最大公约数为3。以上就是欧几里得算法的核心思想，下面代码来实现一下

int gcd(int a, int b) { int r = a % b; while(r) { a = b; b = r; r = a % b; } return b;}

上面的是非递归方法的实现，其实用递归方法代码更简洁，如下

int gcd(int a, int b) { return b ? gcd(b, a % b) : a;}

三. 求最小公倍数

最小公倍数可以通过最大公约数求得，最小公倍数 = 两数之积 / 最大公约数，这个结论我们来证明一下。

根据最大公约数的定义，d是最大的能同时整除a和b的整数，那么a=k1*d，b=k2*d，gcd(k1,k2)=1，那么公倍数满足被a和b整除，那么公倍数必须有k1和k2的乘积，又要要求最小，那么再乘以一个d就是最小的了，即

所以在计算最小公倍数时候，通常只需要先计算出最大公约数就可以了，再通过上述公式就可以求出最小公倍数。

四. 多个数的最大公约数和最小公倍数

有时候，我们不仅求两个数的最大公约数和最小公倍数，还需要求出多个数的最大公约数和最小公倍数，这个其实也不难，多个数的求法可以转化为两两求然后合并即可。

例如求整数a、b、c、d的最大公约数，那么先求出a和b的最大公约数，假如为m1，接下来再求m1和c的最大公约数，假如为m2，最后再求m2和d的最大公约数m3，最终m3就是整数a、b、c、d的最大公约数。最小公倍数的方式也一样，就不列举了。

后面会持续更新更多数论的算法理论知识，欢迎大家多关注！