/*
* -------------------------
* 유클리드 호제법 *
* -------------------------
*/
#include <stdio.h>
int main(void)
{
int a,b,m,n;
printf("두 정수를 입력하세요. : ");
scanf("%d %d", &a, &b);
m=a; n=b;
while (m!=n){
if (m>n)
m=m-n;
else
n=n-m;
}
printf("최대공약수 = %d\n", m);
return 0;
}
// 실행결과
두 정수를 입력하시오 : 128 72
최대공약수 = 8
// 기계적인 반복으로 최대공약수를 구하는 방법인 컴퓨터 지향 알고리즘으로는
유클리드(Euclid)호제법이 있다. 알고리즘을 간단히 정리하면 다음과 같다.
1. m과 n이 같지 않으면 다음을 반복한다.
2. m>n이면 m-n, 그렇지 않으면 n=n-m이다.
3. m(또는 n)이 구하고자 하는 최대공약수 다.