[알고리즘] 최대공약수와 최소공배수 구하기, 유클리드 호제법

유클리드 호제법

 

• 최대공약수 GCD와 최소공배수를 구하는 방법 
• a,b ∈ ℤ 이고, r = a mod b (a를 b로 나눈 나머지)라고 가정하면 r 은 (0 ≤ r < b)이고 a ≥ b 이다.
  그러면 이때 a와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같아지고
  이는 다음과 같다.
  
  GCD(a, b) = GCD(b, r)

 

 

 

 

 

예시

1. a = 64, b = 42 일 경우

GCD(64, 42)일 때 r = 22이고  GCD(64, 42) = GCD(42, 22)이다.

GCD(42, 22)를 보면 r = 20 이고 GCD(42, 22) = GCD(22, 20)이다.

GCD(22, 20)을 보면 r = 2 이고 GCD(22, 20) = GCD(20, 2)이다.

GCD(20, 2)을 보면 r = 0 이고 GCD(20, 2) = GCD(2, 0)이다.

 

GCD(64, 42) = GCD(42, 22) = GCD(22, 20) =  GCD(20, 2) = GCD(2, 0) = 2

결과적으로 나머지가 없다는 것은 공통된 약수로 나누어 떨어진다는 의미이므로 2가 최대공약수가 된다. 

 

 

2. a = 19332, b = 1368 일 경우

19332 ＝ 1368×14 ＋ 180
 1368 ＝ 180×7 ＋ 108
  180 ＝ 108×1 ＋ 72
  108 ＝ 72×1 ＋ 36
   72 ＝ 36×2 ＋ 0

 

(19332, 1368)일 때 r = 180이고  (19332, 1368) = (1368, 180)이다.

(1368, 180)를 보면 r = 72 이고 (1368, 180) = (180, 72)이다.

(180, 72)을 보면 r = 36 이고 (180, 72) = (72, 36)이다.

(72, 36)을 보면 r = 0 이고 (72, 36) = (36, 0)이다.

 

(19332, 1368) = (1368, 180) = (180, 72) = (72, 36) = (36, 0) = 36

따라서 36이 최대공약수가 된다.

 

 

최소공배수

A = a × d, B = b × d 에서 a 와 b 는 서로소이고 d 가 최대공약수라고 하면 두 수의 '소인수분해'를 한 결과의 공통된 부분이 d 이다.

그러면 두 수의 최소공배수는 a × b × d 일 것이다.

 

만약 A와 B로 주어진다면 A = a × d, B = b × d 이므로  a × b × d 를 만족하려면 A × B 만 하면 a × d × b × d 로 d가 한 번 더 들어가 있으니 A × B ÷ d 를 해주면 최소공배수인 a × b × d 를 구할 수 있다.

 

최소공배수는 최대공약수를 구해준 뒤 입력받은 두 수의 곱에서 최대공약수를 나눠주면 끝난다.

 

 

 

코드

// 최대공약수 (반복문)
int gcd(int a, int b) {
	while(b != 0) {
		int r = a % b;
        
		a = b;	// (a, b) = (b, r)	
		b = r;
	}
	return a;
}
 
// 최대공약수 (재귀)
int gcd(int a, int b) {
	if(b == 0) return a;
	return gcd(b, a % b); // (a, b) = (b, r), r = a % b
}
 
// 최소공배수
int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

 

(a, b) = (b, r) 이므로 반복문이나 재귀를 돌 때 a 자리에 b를, b 자리에 r (a % b) 를 대입하는 모습을 볼 수 있다.

 

 

---

출처 : 티스토리 st-lab (직접 읽어보기 강추!), 위키피디아