[알고리즘] 최대 공약수, 최소공배수

최대 공약수를 구하는 알고리즘 중 가장 유명한 유클리드 호제법에 대해 알아보자.

 

유클리드 호제법

   a를 b로 나눈 나머지를 r이라고 할 때, GCD(a, b) = GCD(b, r)이다. r이 0일 때의 b가 최대 공약수이다.

위의 정의를 GCD(24, 16)을 통해 알아보자.

1. 24(a)를 16(b)로 나눈다. 24 % 16 = 8(r)

2. 16(b)를 8(r)로 나눈다.

3. 8(b)와 0(r)을 계산해야 하는데 r = 0이므로 이 때의 b값인 8인 최대 공약수가 된다.

 

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

 

최소공배수 

   최소공배수는 LCM이라고 하며 GCD를 응용해서 구할 수 있다. 

최소 공배수 = g * (a/g) * (b/g);            // g = 최대 공약수
                    = a * b / g