2011/10/11

[C++]求解兩數GCD、LCM (遞迴)


用遞迴來寫其實比較容易體會輾轉相除的過程

#include <cstdlib>
#include <iostream>

using namespace std;

int GCD(int a,int b)
{
    if(b == 0)
    {
        return a;
    }
    else
    {
        return GCD(b, a%b);
    }
}
int main(int argc, char *argv[])
{
    int m, n;
    cout << "請輸入第一個數:";
    cin >> m;
    cout << "請輸入第二個數:";
    cin >> n;
 
    int GetGcd = GCD(m,n);
    cout << "GCD: " << GetGcd << endl;
    cout << "LCD: " << GetGcd*(m/GetGcd)*(n/GetGcd) << endl;
 
    system("PAUSE");
    return EXIT_SUCCESS;
}