C 언어, 유클리드 호제법으로 최대공약수 구하기

C 언어, 유클리드 호제법으로 최대공약수 구하기

 

글. 오상문 sualchi@daum.net

 

예를 들어 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

 

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

 

<출처: https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 >

 

 

다음 예제는 유틀리드 호제법으로 최대공약수를 구하는 C 소스이다.

 

#include <stdio.h>

 

int gcd(int a, int b)
{
  int tmp;
 
  do {
    tmp = a%b;
    a = b;
    b = tmp;
 } while(tmp);
 
  return a; 
}

 

int main()
{
  printf("%d,%d 최대공약수: %d\n", 1071, 1029, gcd(1071, 1029));
  return 0;
}

 

<이상>