유클리드 호제법(Euclidean Algorithm)

최대 공약수 찾기

GCD(Greatest Common Divisor) 메소드

호제법(互除法) : 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘

- 반복문 사용

public static int gcd(int a, int b) {
        // b가 0이 될 때까지 반복
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        // b가 0이 되면 a가 최대공약수가 됨
        return a;
    }

-재귀 호출

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

-메커니즘

• a를 b로 나눈 나머지를 r이라 가정 (r = a % b)
• 만약 r이 0이라면, b가 a와 b의 최대공약수이다. (GCD(a, b) = b)
• 만약 r이 0이 아니라면, a에는 b를, b에는 r을 대입하고 이를 반복한다. (GCD(a, b) = GCD(b, r))

→ 24 % 42 이던지 42 % 24 로 넣던지 상관이 없다. 24 % 42는 다음 차례에 42 % 24로 바뀌게 된다.

예제 ( 출처 : wikipedia )

1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어 떨어진다.

따라서, 최대공약수는 21이다.

78696과 19332의 최대공약수를 구하면,

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

따라서, 최대공약수는 36이다.