유클리드 호제법 - 최대공약수 쉽게 구하는 법

유클리드의 호제법은 소인수분해가 쉽지 않은 '양의 정수'의 최대공약수를 쉽게 구할 수 있는 방법이다.
예를 들어 589와 713의 최대공약수는 쉬워 보이지 않는다.
그러나 유클리드의 호제법을 이용하면 쉽게 풀 수 있다.
유클리드의 호제법은 나머지가 '0'이 될 때까지 나누고 또 나누는 과정을 되풀이 한다.


그렇다면 713과 589의 최대공약수를 유클리드의 호제법을 이용해 한번 풀어 보자.

713 % 589 = 1 ..... 124  -----①
589 % 124 = 4 ..... 93   -----②
124 % 93   = 1 ..... 31   -----③
93   % 31   = 3 ..... 0    -----④

∴ 713과 589의 최대공약수는 31이다.

이러한 방법으로 최대공약수를 구하면 쉽게 구할  수 있다.

출처 : 소설처럼 아름다운 수학 이야기_김정희 지음

간단한 C코드

#include <stdio.h>

int GCMU(int num1, int num2);
int main(void){
  int num1, num2, result;
 printf("2)최대공약수를 출력하는 프로그래밍을 작성해 보자\n");
 printf("두 정수를 입력하여라 : ");
 scanf("%d   %d", &num1, &num2);
 result = GCMU(num1, num2);

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

 return 0;
}

int GCMU(int num1, int num2)
{
 if(num2 == 0 ) return num1;
 else
  return GCMU(num2, num1 % num2);
}