이번 글에서는 두 정수의 최대 공약수 구하기를 유클리드 호제법과 재귀함수를 이용하여 구현해 본다.

유클리드 호제법 이란?

두 정수 a, b의 최대공약수의 값을 gcd(a, b)라고 하면 gcd(a, b) => gcd(b, a%b) = gcd(b, r) 이다.
(위 식에서 r은 a/b의 나머지인 a%b이다.)

• 예시1 : 최대공약수가 있는 경우
  gcd(30, 12) => gcd(12, 30%12)
  gcd(12, 6) => gcd(6, 12%6)
  gcd(6, 0)

따라서 30과 12의 최대공약수는 6이다.

• 예시2 : 최대공약수가 없는 경우
  gcd(9, 7) => gcd(7, 9%2)
  gcd(7, 2) => gcd(2, 7%2)
  gcd(2, 1)

따라서 9와 7의 공약수는 없다.

유클리드 호제법을 이용하여 최대공약수를 구할 때 재귀함수가 끝나는 조건이 될 때까지 위의 과정을 계속 반복한다.
재귀함수를 끝내기 위한 조건은 나머지가 0 이거나 두 정수 중 한개가 1이 된 경우이다.

위의 식을 일반화한 규칙으로 표시하면 아래와 같다.

gcd(a, b) = (b, a%b)

private static int gcd(int a, int b) {

    // 두 정수 중 뒤의 수(나머지)가 0 이면, 앞의 수가 공약수이다.
    if(b == 0)
        return a;

    // 두 비교 수 중에 1이 있으면, 공약수가 없다.
    if(a == 1 || b == 1)
        return 1;
    
    // 다음 함수 값을 정할 때 작은 수는 앞에 큰수를 작은수로 나눈 나머지는 뒤에
    if(a > b)
        return gcd(b, a%b);
    else
        return gcd(a, b%a);        
}

소스보기

소스로딩 실패

실행결과