C 언어, 최대 공약수(GCD) 구하는 다양한 방법

C 언어, 최대 공약수(GCD) 구하는 다양한 방법

 

글. 오상문 sualchi@daum.net

 

다음은 최대공약수를 구하는 세가지 방법을 보여주는 예제입니다.

 

#include <stdio.h>

 

// 나머지 연산 이용
int gcd1(int a, int b)

{
  int i;
  if (a > b) { i = a; a = b; b = i; }
 
  for(i = a; i > 0; i--)
    if(a % i == 0 && b % i == 0)
      return i;

  return 1; 
}

 

// 빼기 연산 이용
int gcd2(int a, int b)

{
  int i;

 

  while(a != b) {
    if(a > b)
      a -= b;
    else
      b -= a;
  }
   return a;
}

 

// 유클리드 호제법
int gcd3(int a, int b)

{
   if (b == 0)
     return a;

   return gcd3(b, a % b);
}

 

int main()

{
  int n1 = 20, n2 = 12;
 
  printf("%d, %d 최대공약수는 %d \n", n1, n2, gcd1(n2, n1));
  printf("%d, %d 최대공약수는 %d \n", n1, n2, gcd2(n2, n1));
  printf("%d, %d 최대공약수는 %d \n", n1, n2, gcd3(n2, n1));
 
  return 0;
}