[C/C++基礎]- 利用遞迴方式求最大公因數和求其最小公倍數 – jashliao部落格

程式碼

#include 

usingnamespace std;

/*

利用遞迴方式求最大公因數和求其最小公倍數

*/

int gcd_1(int a,int b)//求最大公因數_1_以輾轉相減法

{

    if(a==b)

        return a;

    if(a>b)

        return gcd_1(a-b,b);

    return gcd_1(a,b-a);

}

int gcd_2(int a,int b)//求最大公因數_2_以輾轉相除法

{

    int c=0;

    c=a%b;

    if(c==0)

        return b;

    return gcd_2(b,c);

}

int lcm(int a,int b)//求其最小公倍數

{

    return b/gcd_1(a,b)*a;

}

void main(void)

{

    int a,b,c;

    a=30,b=45;

    c=gcd_1(a,b);

    cout<

    c=gcd_2(a,b);

    cout<

    c=lcm(a,b);

    cout<

}