[CS][알고리즘] 유클리드 호제법

정의

• 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘
• 호제법 : 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘

- a % b = r 이라고 할때, a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.
- 이를 이용해 b % r = r' , r' % r''을 반복해 나머지가 0이 되는 '나누는 수'가 두 수 a와 b의 최대공약수 이다.

예시

• 84와 68의 최대공약수
  1. 84와 68는 나누어 떨어지지 않으므로 84 % 68 = 16
  2. 68 % 16 = 4 , 16 % 4 = 0
  3. 나머지가 0이 되는 나누는 수 » 4
  4. 두 수의 최대 공약수는 4이다.

알고리즘

public static int func(int a, int b) {
        if(a>=b) {
            if(b==0) return a;
            return func(b, a%b);
        } else {
            if(a==0) return b;
            return func(a, b%a);
        }
    }

최소 공배수

• 최소공약수를 구하는 유클리드 호제법을 이용해 두 수의 최소 공배수도 구할 수 있다.
• 최소공배수 = 최대공약수 * (a / 최대공약수) * (b / 최대공약수)