利用欧几里德算法求解最大公约数

                                            上海传智播客  崔长春老师

利用欧几里德算法求两个正整数的最小公倍数又叫辗转相除法，他是基于如下定理：

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

   例如：两个数15和12，两数相除得余数为3，12和余数3这两个数的公约数为3，则15和12这两个数的最大公约数就等于3.

很显然，根据上述定理，程序设计可以考虑两种实现方式，就是递归和循环。递归实现：

function gcd($max,$min){

                if($min==0){ return $max; }

                return gcd($min,$max % $min);

        }

        $num=gcd(40,12);

        echo $num;//结果：4

循环实现：

function gcd($max,$min){

                do{

                        $mod = $max % $min;

                        $max = $min;

                        $min = $mod;

                }while($mod != 0);

                return $max;

        }

        $num=gcd(55,35);

        echo $num;//结果：5  

很不错，受教了