最大公约数和最小公倍数的算法

3.欧几里得算法,即gcd(m,n) = gcd (n,m mod n);gcd是greatest common diviso（最大公约数）的缩写，gcd(m ,n ) 表示m和n的最大公约m mod n代表m除以n后的余数.重复以上等式直到m mod n=0；因为gcd(m,0) = m,m最后的取值就是m和n的初值的最大公约数。
（也有人叫这辗转相除法）
伪代码描述如下:
Euclid(m,n)
//使用欧几里得算法计算gcd(m,n)
while n != 0 do
    r = m mod n
    m = n;
    n = r
return m
4.stein算法  虽然前两种算法都能求出结果，但它们都有一定的优缺点。第一种穷举法虽然最好理解，但计算量最大。第二种欧几里德算法是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。

    现在的硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。

Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。

首先需要了解的是：一个奇数的所有约数都是奇数。我们来研究一下最大公约数的性质，我们发现有 gcd( k*m,k*n ) = k*gcd( m,n) 这么一个非常好的性质（证明就省去了）。说他好是因为他非常符合我们化小的思想。我们试取 k=2 ，则有 gcd( 2m,2n ) = 2 * gcd(m,n)。这使我们很快联想到将两个偶数化小的方法。那么一奇一个偶以及两个奇数的情况我们如何化小呢？

我们来看看一奇一偶的情况：设有2x和y两个数，其中y为奇数。因为y的所有约数都是奇数，所以 a = gcd( 2m,n) 是奇数。根据2x是个偶数不难联想到，a应该是x的约数。我们来证明一下：(2m)%a=0，设2m=n*a，因为a是奇数，2x是偶数，则必有n是偶数。又因为 m=(n/2)*a，所以 m%a=0，即a是m的约数。因为a也是n的约数，所以a是m和n的公约数，有 gcd(2m,n ) <= gcd(m,n)。因为gcd(m,n)明显是2m和n的公约数，又有gcd(m,n) <= gcd(2m,n)，所以 gcd(2m,n) = gcd(m,n)。至此，我们得出了一奇一偶时化小的方法。

再来看看两个奇数的情况：设有两个奇数m和n，似乎m和n直接向小转化没有什么太好的办法，我们可以绕个道，把m和n向偶数靠拢去化小。设m>n，我们注意到m+n和m-n是两个偶数，则有 gcd( m+n,m-n) = 2 * gcd( (m+n)/2,(m-n)/2 )，那么 gcd(m,n) 与 gcd(m+n,m-n) 以及 gcd( (m+n)/2,(m-n)/2 ) 之间是不是有某种联系呢？为了方便设 x=(m+n)/2 ，y=(m-n)/2 ，容易发现 x+y=m ，x-y=n 。设 a = gcd(x,y)，则 x%a=0,y%a=0 ，所以 (x+y)%a=0，(x-y)%a=0 ，即m%a=0 ，n%a=0 ，所以a是m和n的公约数，有 gcd(m,n)<= gcd(m,n)。再设 b = gcd(m,n)肯定为奇数，则 m%b=0,n%b=0 ，所以 (m+n)%b=0 ，(m-n)%b=0 ，又因为m+n和m-n都是偶数，跟前面一奇一偶时证明a是m的约数的方法相同，有 ((m+n)/2)%b=0,((m-n)/2)%b=0 ，即 x%b=0 ，y%b=0 ，所以b是x和y的公约数，有 gcd(m,n) <= gcd(x,y)。所以 gcd(m,n) = gcd(x,y) = gcd( (m+n)/2,(m-n)/2 )。
我们来整理一下，对两个正整数 m>n：
1.均为偶数 gcd(m,n) =2gcd(m/2,n/2)；
2.均为奇数 gcd(m,n) = gcd( (m+n)/2,(m-n)/2 )；
2.m奇n偶   gcd(m,n) = gcd(m,n/2)；
3.m偶n奇   gcd(m,n) = gcd(m/2,n)  或 gcd(m,n)=gcd(n,m/2 )；

现在我们已经有了递归式，还需要再找出一个退化情况。我们用这个： gcd(m,m) = m。

最小公倍数的求法有二：
1.适合数不太大时直接求最小倍数的题。其实和二是一样的道理。

已知m,n均为正整数，试用C语言写出求m与n的最小公倍数的算法，算法的步骤为：
（1） 计算m*n的积，送临时变量r。
（2） 若m等于n，则输出最小公倍数r/m，算法结束。
（3） 若m大于n，计算m-n，结果送m，否则，计算n-m，结果送n。(即max = max - min)
（4） 转到（2）或者（3）。

2.lcm(m,n) = m*n/gcd(m,n),即两个数的积除以它们的最大公约数。这个适合已知最大公约数时。

以上是两个数的最大公约数和最小公倍数的算法，其实n个数的算法也是类似的，只需要类推就是了：
int gcd(int, int); //两个数的最大公约数
int ngcd(int *, int) //N个数的最大公约数
int lcm(int, int) //两个数的最小公倍数
int nlcm(int *, int) //N个数的最小公倍数


int gcd(int a, int b)
{
if(a < b) //swap(a,b)
{
a = a ^ b;
b = a ^ b;
a = a ^ b;
}

int c;
while((c = a % b) != 0) //辗转相除
{
a = b;
b = c;
}
return b;
}

int ngcd(int * pa, int n)
{
if(n == 1)
return *pa;
return (gcd(pa[n-1], ngcd(pa, n-1)));
}

int lcm(int a, int b) //最大公倍数 ＝ 两数乘积 / 最大公约数
{
return a*b/gcd(a, b);
}

int nlcm(int * pa, int n)
{
if(n == 1)
return *pa;
return lcm(pa[n-1], nlcm(pa, n-1));
}