今天在群里看到有朋友提出一道面试题，是如何求得2个数的最大公约数。在《Javascrit权威指南》一书曾今中有提到相关的例子,其原理是使用欧几里得算法求得。

在数学中，欧几里得算法，又称辗转相除法，是求两个正整数的最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》中，而在中国则可以追溯至东汉出现的《九章算术》。其定理为：

gcd(a,b) = gcd(b,a%b)

即设两数为a、b，其中a>b，a%b为a除以b以后的余数且a%b不为0，用gcd(a,b）表示a和b的最大公约数。也就是说，两个数的最大公约数=（较小的数）和（较大的数除以较小的数的余数）的最大公约数。

基于上述等式，我们先来求 a=481 和 b=221 的最大公约数，解剖欧几里德算法计算过程：

假设f为a和b的最大公约数
a除以b的余数 等于 481%221 等于 39

根据公式，那么f也等于221和39的公约数，我们继续求模
221除以39的余数 等于 221%39 等于 26

根据公式，f也等于39和26的公约数 ，我们继续求模
39除以26的余数数 等于 39%26 等于 13

根据公式，f 也等于26和13公约数，我们继续求模
26除以13的余数数 等于 39%26 等于 0

到这一步，26可以13被整除，说明他们的最大公约数也就是13，即f=13。

通过这个等式，我们可以一步一步地缩小与原始数公约数相同的的一对数字，最后直到找到较大数能被较小数整除为止，那么较小数就是他们的最大公约数。

在javascript中我们可以通过一个while循环来实现这个计算过程：

function gcd(a, b){
        var t; //临时变量，用于储存值
        if(a<b){ //交换，确保a>=b
            t = b;
            b = a;
            a = t;
        }
        while(b!=0){
            t = b;
            b = a%b;
            a = t;
        }
        return a;
    }
    gcd(481, 221); //13

或者我们可以通过一个递归来实现类似的计算：

function gcd2(a, b){
        var t;
        if(a<b){
            t = b;
            b = a;
            a = t;
        }
        if(b != 0){
            return arguments.callee(b,a%b);
        }
        return a
    }
    gcd2(481, 221); //13