유클리드 호제법 (Euclidean Algorithm) in C

유클리드 호제법은, 두 정수의 최대 공약수(Greatest Common Divisor)를 구하는 알고리즘 중 하나이다.
a, b의 최대 공약수는, a/b를 나눈 나머지인 r과 b의 최대공약수와 같다는 성질에 따라, 재귀와 반복문을 통해 구현할 수 있다.

 

* 최대 공약수 ( Greatest Common Divisor, GCD )
두 개 이상의 수가 공통으로 갖고 있는 약수 중 가장 큰 ! 수.
ex) 
8의 약수 : 1, 2, 4, 8
12의 약수 : 1, 2, 3, 4, 6, 12
8과 12의 최대 공약수 : 4

* 최소 공배수 ( Least Common Multiple , LCM )
ex)
3의 배수 : 3, 6, 9, 12, 15 ...
5의 배수 : 5, 10, 15, 20 ...
3과 5의 최소 공배수 : 15

 

좀 더 구체적으로, 비교대상의 2개의 자연수 a와 b 에서, ( 단 a > b ) a를 b로 나눈 나머지를 r이라고 했을 때,

GCD(a, b) = GCD(b, r) 과 같고, 

" r이 0이면 그 때 b가 최대 공약수이다! " 라는 원리를 활용한 알고리즘이다. 

ex)
GCD( 24, 16 ) -> GCD( 16, 8 ) -> GCD( 8, 0 ) : 최대 공약수 = 8 
GCD( 55, 22 ) -> GCD( 22, 11 ) -> GCD( 11, 0 ) : 최대 공약수 = 11

 

# 재귀 함수 활용 

#include <stdio.h>

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

int main(void)
{
    printf("%d\n", Euclidean(11, 10);
	return 0;
}

 

# 반복문 활용

#include <stdio.h>

int Euclidean(int a, int b)
{
	while(1) {
    	int r = a%b;
        a = b;
        b = r;
        if( b == 0) break;
    }
    return a;
}

int main() {
	printf("%d\n", Euclidean(11,10));
    return 0;
}

 

# 다항식 활용

int a = 8;
int b = 16;
int c = 24;

int result = GCD(a,b);
result = GCD(result, c);
printf("%d\n", c);

 

# 장점 : 빠르다 ! 일반적으로는 일일히 나눠줘야하는 O(N)인데 유클리드 호제 쓰면 시간 복잡도가 O(logN) 이다. 

# 단점 : 최대 공약수는 빠르게 산출이 가능한데, 최소 공배수를 계산함에 있어서는 좀 다르기 때문, !

 

# 최소 공배수 구하기

int LCM(int a, int b)
{
	return a * b / GCD(a,b);
}

GCD를 구하는 알고리즘을 먼저 유클리드 호제법을 활용하여 구현한 뒤에, 

a * b / GCD( a, b ) 를 해주면 최소 공배수를 구할 수 있다!