最大公因数&最小公倍数

求最小公因数

辗转相除法

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

int gcd(int a,int b)
{
    do
    {
        int t;
        t=a%b;
        a=b;
        b=t;
    }while(b);
        return a;
}

递归思想

int gcd(int a, int b){   //定义函数 
    if(a % b == 0)    
        return b;
    return gcd(b, a%b);   //辗转相除法 
}

朴素算法
（递归思想先归后递

int gcd(int a,int b)
{
    int i;
    for(i=a;i>=1;i--)
    {
        if(a%i==0 && b%i==0)
            return i;
    if(a>b)
        return gcd(b,a);
    }
}

求最小公倍数
等于 a * b / gcd(a,b)