유클리드 호제법 알고리즘, 최대공약수, 최소공배수

유클리드 호제법이란?

---

두 수의 최대 공약수를 구하는 알고리즘의 하나.

 

2개 자연수 a, b ( a > b )에 대해 a를 b로 나눈 나머지를 r이라 하면,

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

또 다시 b , r 에 대해 b를 r로 나눈 나머지 r' 을 가지고 위의 과정을 반복해 나머지가 0이 되었을 때

나누는 수가 a와 b의 최대 공약수.

 

( a , b ) = ( b , r (=a%b)  )  = ( r , r' )

 

( 1071 , 1029 ) = ( 1029 , 42 ) = ( 42 , 21 ) = ( 21 , 0 ) = 21

21은 1071과 1029의 최대 공약수

 

 

 

GCD 관련 법칙

• GCD( u , v ) = GCD( u - v,  v )  if u < v
• GCD( u, v ) = GCD( v ,u )
• GCD ( u , 0 ) = u

 

 

 

알고리즘

---

1. a , b (a > b) 가 입력으로 들어온다.

2. b == 0 이면 a 리턴 

3. 아니라면  b ,a%b 로 다시 반복

 

소스 코드

//recursive 
int GCD1(int a,int b){
	return b? GCD(b,a%b) : a;
} 

int GCD2(int a, int b){
	int tmp;
	while(a%b){
		tmp = a/b;
		b = a%b;
		a = tmp;
	}
	return a;
}

 

 

호제법 확장

---

정수의 경우

정수 m , n 의 최대 공약수 GCD(m,n) 구할 때 확장된 유클리드 호제법 이용하면

am + bn = GCD(m,n) 의 해되는 a,b 짝 찾을 수 있다.

이 식을 베주의 정의 

 

최소공배수 구하기

//최소 공배수
int LCM(int a, int b){
	return a*b/GCD(a,b);
}

 

 

계산량

---

최악의 경우라도 작은 수(십진법) 자리수의 5배 반복하기 전에 최대공약수에 이른다(라메의 정리)

 

최대공약수 구할 때 소인수분해보다 유클리드 호제법으로 구하는 것이 더 빠름.

최대공약수 구하는 것은 쉬운 문제, 소인수 분해가 더 어려운 문제.

 

2개의 정수의 비트수를 n,

유클리드 알고리즘은 Θ(n) 회의 나눗셈으로 최대공약수 구할 수 있음.

 

 

---

참고

유클리드 호제법 위키

최대공약수 최소공배수 알고리즘