最大公约数的三种求法（C语言练习实例16）

题目：输入两个正整数m和n，求其最大公约数和最小公倍数。

一.更相减损

int gcd(int a,int b)
{
    if(a==b)
        return a;
    else if(a>b)
        return gcd(a-b,b);
    else
        return gcd(b-a,a);
}

二.辗转相除

迭代写法：

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

递归写法：

int gcd(int a, int b)    //a > b
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}

获取最大的方法除了判断交换外，还可如下操作：

int sum=a+b;
a=a>b?a:b;
b=sum-a;

递归写法简化：

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