[코테준비] C++ 최소공배수, 최대공배수(유클리드 호제법) 구하기

int gcd(int a, int b) {
    int c;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

최대공약수를 구하면 최소공배수는 구하기 쉽다.

a=12 b=8

GCD(12,8) - GCD(8,12%8) - GCD(8,4) - GCD(4,0)

최대공약수 = 4

 

최소공배수 = a*b/최대공약수