[Algorithm] GCD (최대 공약수) & LCM (최소 공배수)

GCD

"2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다."

LCM

"두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다. "

#include <iostream>
using namespace std;

// 최대 공약수
int GCD(int a,int b) {
    if(b == 0) return a;
    return GCD(b,a%b);
}

// 최소 공배수
int LCM(int a, int b) {
    return a * b / GCD(a,b);
}

int main() {
    // 여기에 코드를 작성해주세요.
    int a,b; cin >> a >> b;
    cout << LCM(a,b) << endl;
    return 0;
}