# GCD&LCM

## 最大公因數

求法:輾轉相除法,直到較小的數為0,則另一個數為最大公因數

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

簡短版

int gcd(int a,int b){  //a<b
    return a==0?b:gcd(b%a,a);
}

直接呼叫C++內建函式

cout << gcd(12,16) << '\n'; //4

## 最小公倍數

兩數相乘,除以最大公因數

lcm(a,b)=a*b/gcd(a,b)

int a=12,b=16;
cout << a*b/gcd(a,b);  //48