对于 52317 和 75569 两个数，你能迅速地求出它们的最大公约数吗？一般来说你会找一

 

找公共的使因子，这题可麻烦了，不好找，质因子大。

 

现在教你用辗转相除法来求最大公约数。

先用较大的 75569 除以 52317，得商 1，余数 23252，再以 52317 除以 23252，得商 2，余
数是 5813，再用 23252 做被除数，5813 做除数，正好除尽得商数 4。这样 5813 就是 75569
和 52317

 

的最大公约数。你要是用分解使因数的办法，肯定找不到。

 

那么，这辗转相除法为什么能得到最大公约数呢？下面我就给大伙谈谈。

比如说有要求 a、b 两个整数的最大公约数，a＞b，那么我们先用 a 除以 b，得到商 8，余
数 r1：a÷b＝q1…r1 我们当然也可以把上面这个式子改写成乘法式：a＝bq1＋r1------l  

）

如果 r1＝0，那么 b 就是 a、b 的最大公约数 3。要是 r1≠0，就继续除，用 b 除以 r1，我们也

 

可以有和上面一样的式子：

b＝r1q2＋r2-------2

 

）

如果余数 r2＝0，那么 r1 就是所求的最大公约数 3。为什么呢？因为如果 2）式变成了 b＝
r1q2，那么 b1r1 的公约数就一定是 a1b 的公约数。这是因为一个数能同时除尽 b 和 r1，那
么由 l）式，就一定能整除 a，从而也是 a1b

 

的公约数。

反过来，如果一个数 d，能同时整除 a1b，那么由 1）式，也一定能整除 r1，从而也有 d
是 b1r1

 

的公约数。

这样，a 和 b 的公约数与 b 和 r1 的公约数完全一样，那么这两对的最大公约数也一定相同。
那 b1r1 的最大公约数，在 r1＝0 时，不就是 r1 吗？所以 a 和 b 的最大公约数也是 r1

 

了。

有人会说，那 r2 不等于 0 怎么办？那当然是继续往下做，用 r1 除以 r2 ……

，

直到余数为

 

零为止。

在这种方法里，先做除数的，后一步就成了被除数，这就是辗转相除法名字的来历吧。

int gcd( int n, int m ) 
{ 
if( m == 0 ) return n; 
return gcd( m, n % m ); 
} 

 

呵呵，够简单吧！
这个是辗转相除的递归形式~ 
至于辗转相除，可以 baidu

  

下，有很多介绍