최대공약수, 최소공배수

두 수의 최대공약수를 구하는 알고리즘은 유클리드 호제법을 베이스로 한다.

78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
1368 ＝ 180×7 ＋ 108
180 ＝ 108×1 + 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2

gcd = 36

출처

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 

 

큰 수(a)에서 작은 수(b)로 나누어 그 나머지(r)가 존재하면 

작은 수에서 그 나머지로 나누는 과정을 나머지가 없을 때 까지 재귀적으로 반복하는 것이다.

int gcd(int a, int b) // always a > b
{
	//
    int remainder;
    while((remainder = a % b))
    {
    	//
        a = b;
        b = remainder;
    }
    
    return b;
}

 

두 수의 최소공배수는 두 수의 최대공약수를 안다면 쉽게 구할 수 있다.

int lcm(int a, int b) // always a > b
{
	//
    return ((a * b) / gcd(a, b));
}

두 수를 곱하면, 중복인수가 생겨서 이를 최대공약수로 나누어 주는 것이다