유클리드 호제법 (Euclidean algorithm)

유클리드 호제법이란?

---

- 유클리드가 집필한 '유클리드 원론'에 나오는 최대공약수를 찾는 기법이다.
- 호제법 의미, 互(서로호), 除 (덜 제)를 사용한 단어로 두 숫자를 상호 나누거나 빼서

"최대공약수"를 찾는다.

1. 호제법의 이해

(1) 호제법을 어떤 function 이나 Method 라고 생각해본다

• input : 임의의 숫자 2개 (각 a, b 라고 가정)
• output : 두수의 최대공약수 숫자 1개 (x 라고 가정)

// 코드로 표현하면 이런식 
public int gcd(int a, int b) { 
	return 최대공약수; 
}

 

(2) input, output을 어떻게 정의해야할지 고민해본다

 

(3) input a, b는 자연수가 입력되어야한다.

• input a, b는 int로 정의했다. (숫자기만 하면된다 long 도 상관없다.)
• int는 32bit 정수형이기 때문에 [–2,147,483,648 ~ 2,147,483,647] 범위 안에 포함된다
• 음수의 최대공약수는 구할 수 없다. (구지 구한다면 절대값을 취한다던지 규칙이 필요하다)
• 그래서 우리는 최대공약수 계산시 필요한 input 값을 양수로 보장할 필요가있다

 

(4) 모든 자연수는 소수의 곱으로 이루어져 있다.

• a = 24 = 2 * 2 * 2 * 3
• b = 32 = 2 * 2 * 2 * 2 * 2
• c = 40 = 2 * 2 * 2 * 5
• 소수곱에 대한 이야기를 Matrix 로 표현한다면 아래와 같다.

	2	3	5	7	11	13
a = 24	3	1	0	0	0	0
b = 32	5	0	0	0	0	0
c = 40	3	0	1	0	0	0
d = 49	0	0	0	2	0	0

• 임의의 a, b에 대한 최대공약수는?

	2	3	5	7	11	13
a = 24	3	1	0	0	0	0
b = 32	5	0	0	0	0	0
gcd	min(3, 5)	min(1, 0)	min(0, 0)	min(0, 0)	min(0, 0)	min(0, 0)

• gcd = 2^min(3, 5) * 3^min(1, 0) * 5^min(0, 0) * 7^min(0, 0) * ....
• gcd = 2*2*2 = 8
• 중복되는 소수곱이 최대공약수이다

(5)  a, b를 Mod 연산하여 최대공약수를 구한다

• gcd = 최대공약수
• a = gcd * x  (a 는 gcd의 배수)
• b = gcd * y  (b 는 gcd의 배수)
• gcd 값은 모르지만  a % b = gcd의 배수 이다.
• a % b = gcd * (x % y) 
• a, b, a % b 세가지 수 모두 gcd의 배수
• 내가 궁굼한 것은 gcd 이므로 입력값 a,b 와 상관없이 작은 값 2개를 골라 다시 gcd 한다.
• b % (a%b) = gcd * (y % (x % y)) -> gcd 배수 (하지만 더 작은)
• 위 작업을 gcd * 1 일때까지 반복하면된다.

(6) gcd * 1을 찾는 법

• a % b = 0 일때를 찾으면 된다

(7) 코드로 표현

public class gcd {

	static int DIV = 100;
	
	public static void main(String[] args) {

		int a = (int) (Math.random() * Integer.MAX_VALUE % DIV);
		int b = (int) (Math.random() * Integer.MAX_VALUE % DIV);
		
		System.out.println("a = "+ a+ ", b = "+b);
		System.out.println("gcd = "+gcd(a, b));
	}

	private static int gcd(int A, int B) {
        // B 가 0 이면, 이전 A % B 가 0 이기 때문에 A가 최대공약수 
        // B 가 0 아니면, B, A % B의 gcd 계산
		return B!=0?gcd(B, A%B):A;
	}

}