1. 정의

두 개의 수가 주어졌을 때, 최대공약수를 구하는 알고리즘

2. 예시

3. 코드로 구현

/**
     * 유클리드 호제법 구현 메서드
     * @param bn : 큰 숫자
     * @param sn : 작은 숫자
     * @return
     * 큰 숫자를 작은숫자로 나눈 값이 0이면 작은숫자 리턴, 아니면 재귀형태로 자신을 호출
     */
     
    public int eucd(int bn, int sn) {
        // 큰숫자를 작은숫자로 나눈 나머지를 계산
        int r = bn % sn;
        // 나머지가 0이면 작은숫자가 최대공약수이므로 작은숫자 리턴
        if (r == 0) {
            return sn;
        } else {
            // 나머지가 0 이상이면 재귀형태로 호출
            // 이때 파라미터는 작은숫자와 나머지를 넣어줌
            return eucd(sn, r);
        }
    }

• A, B 두 수의 최소 공약수를 구하고
  A * B / 최대 공약수 = 최소 공배수 가 나온다

참고: [Algorithm] 유클리드 호제법을 Java로 구현해보자!! (with BOJ 2609)