[C++] 최대공약수(GCD), 최소공배수(LCM) 구하기

우선 두 수의 최소공배수(LCM)는 두 수의 곱을 최대공약수로 나눠주면 구할 수 있다

따라서 최대공약수(GCD)를 구하는 것이 중요하다

 

a와 b의(단, a > b)최대 공약수는 a % b(mod), 즉 나머지가 0이 될 때까지 아래와 같이 반복하여 구할 수 있다

1. a % b = r, 나머지의 값을 구한다

2. b를 나머지(r)로 나눈 값의 나머지(r')를 구한다

3. r을 r'로 나눈 값의 나머지(r'')를 구한다

...

 

1. 재귀함수로 구현

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

 

2. 반복문으로 구현

int gcd(int a, int b)
{
    int r = a % b;
    while(r)
    {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

 

 

관련 문제

https://www.acmicpc.net/problem/5347