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

 

線上編譯: https://www.tutorialspoint.com/compile_cpp_online.php

本篇要和(C/P)同好分享利用遞迴方式求最大公因數和求其最小公倍數，有興趣的同好歡迎來(C/P)一下哈哈 ^ ^。

Code

/* Online C++ Compiler and Editor */
#include <iostream>

using namespace 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;
}

int main()
{
    int a,b,c;
    a=30,b=45;
    c=gcd_1(a,b);
    cout<<c<<"\n";
    c=gcd_2(a,b);
    cout<<c<<"\n";
    c=lcm(a,b);
    cout<<c<<"\n";
	return 0;
}