유클리드 알고리즘 - 최대공약수, 최소공배수 구하기

두 정수의 최대공약수를 계산하는 방법 중에, 두 정수의 소인수분해를 하여 최대공약수를 구하는 방법이 있다.

 

하지만 두 정수의 소인수분해를 사용하여 최대공약수를 계산하는 방법은 비효율적이다.

소인수분해를 하는 데 시간이 많이 걸리기 때문이다.

 

두 정수의 소인수분해를 하여 최대공약수를 하는 방법보다는 유클리드 알고리즘을 사용해서 최대공약수를 구하는 것이 더 효율적이다.

 

유클리드 알고리즘은 고대 그리스의 수학자 유클리드의 이름을 딴 것이다.

 

유클리드 알고리즘은 다음의 정리를 바탕으로 한다.

 

a, b, q, r이 정수일 때 a=bq+r이라 하자. 그러면 gcd(a, b) = gcd(b, r).

 

이 정리의 증명에 앞서

287과 91의 최대공약수를 찾는 과정을 생각해보자.

 

287 = 91*3 + 14이다.

91과 287을 공통으로 나눌 수 있는 약수를 d라 했을 때, d는 287-91*3 = 14도 나눌 수 있다.

따라서 91과 14를 공통으로 나눌 수 있는 약수는 287 = 91 * 3 + 14를 나눌 수 있다.

그래서 91과 287의 최대공약수는 91과 14의 최대공약수와 같다.

 

이는 91과 287의 최대공약수를 찾는 문제가 91과 14의 최대공약수를 찾는 문제로 축소됨을 의미한다.

 

다음으로,

 

91를 14로 나누면

91 = 14 * 6 + 7이다.

91과 14의 공약수는 91-14*6 = 7을 나누고, 14와 7의 공약수는 91을 나눌 수 있다.

이는 gcd(91, 14) = gcd(14, 7)을 의미한다.

 

계속해서

 

14를 7로 나누면

14 = 7 * 2 이다.

7이 14를 나누므로 gcd(14, 7) = 7이다.

 

종합해서 정리해보면

gcd(287, 91) = gcd(91, 14) = gcd(14, 7) = 7이다.

 

이와 같이 유클리드 알고리즘은 일반적으로 두 양의 정수의 최대공약수를 찾는 문제를 더 작은 정수들의 문제를 축소하기 위해 나눗셈을 어느 한 쪽이 0이 될 때까지 반복한다.

 

다시 처음으로 돌아가서, 유클리드 알고리즘의 기본이 되는 정리를 증명해보자.

 

a, b, q, r이 정수일 때 a=bq+r이라 하자. 그러면 gcd(a, b) = gcd(b, r).

 

a와 b를 나누는 d가 있다고 가정한다. 앞서 계산했던 과정을 통해 d역시 a - bq = r을 나눈다.

마찬가지로, d는 bq + r = a를 나눈다. 그러므로, b와 r의 공약수는 a와 b의 공약수이다.

 

이 알고리즘을 의사코드로 정리해보면 다음과 같다.

 

procedure gcd(a, b : positive integers)

x = a

y = b

while y!=0

r = x mod y

x = y

y = r

return x

 

이 알고리즘을 순서도로 표현하면 다음과 같다.

이 알고리즘을 C언어로 구현하면 다음과 같다.

#include <stdio.h>

#include <stdlib.h>

int main()

{

        int x = 0, y = 0, r = 1;

        int mode = 0;

        while(1) {

                printf("1. 최대공약수 구하기 \n2. 프로그램 종료, -1 입력해주세요.\n");

                scanf("%d", &mode);

                if(mode == -1) break;

                else if(mode == 1) {

                        printf("x와 y의 값을 입력해주세요\n");

                        scanf("%d %d", &x, &y);

                        if(x <= 0 || y <= 0) {

                                printf("숫자가 잘못 입력되었습니다.\n");

                                continue;

                        }

                        else {

                                while(r != 0) {

                                r = x % y ;

                                x = y;

                                y = r;

                                }

                                printf("x와 y의 최대공약수는 %d입니다.\n", x);

                                r = 1;

                        }

                }

                else {

                printf("숫자 잘못 입력하셨습니다.\n");

                continue;

                }

        }

        return 0;

}