최대공약수(GCD), 최대공배수(LCM) 구하기

최대공약수, 최대공배수 구하기 

 

글.  오상문 sualchi@daum.net 

 

1. 최대 공약수(GCD) 구하기 (유클리드 호제법)

 

두 자연수 a, b의 최대 공약수를 구해보자. 

최대 공약수란 a, b를 나누어 떨어지게 하는 가장 큰 공통 정수이다.

그리고 a, b의 최대 공약수는 a 또는 b 보다 클 수 없다.

 

-유클리드 호제법을 이용한 GCD 구하기

 

a=56와 b=12가 주어졌다고 하자. 

 

a를 나누면 4가 몫이고 8이 나머지이다. 즉, 다음과 같다.
a = b*4 + 8           ---> a = b*q + r 형태가 된다.

 

이제 a에 b를 넣고 b에 나머지를 넣는다. 이제 a = 12, b = 8

다시 앞처럼 계산하면...
a = b*1 + 4   
      
이제 a에 8을 넣고 b에 4를 넣는다.
나머지가 0이 될 때까지 반복하자.

a = b*2 + 0    --> 드디어 나머지가 0이다.  a = 4, b = 0

 

최종 a 값, 즉 4가 최대공약수이다.  

 

int GCD(int a, int b) {  
  if (b == 0)  
    return a;
  return GCD(b, a%b);
}

 

int main() {
   int gcd;
   gcd = GCD(56, 12);
   return gcd;
}

 

[참고]  두 정수는 크기 순서 상관없이 입력할 수 있다.
나머지 연산을 하면서 자동으로 크기 순으로 정렬되는 효과를 얻기 때문이다.

 

 

// long long 버전 GCD 함수는 다음과 같다.

long long GCD(long long a, long long b) {  
  if (b == 0)  
    return a;
  return GCD(b, a%b);
}

 

 

- 빼기를 이용한  GCD 구하기 

 

큰 수에서 작은 수를 빼는 방법을 이용하여 GCD를 구한다.

 

#include <stdio.h>

 

int GCD (int a, int b) { 
  if(a<1 || b<1)            // 1보다 작은 수가 있으면 되돌아감
    return 0;
  if(a == 1 || b == 1)     // 1인 수가 있으면 1이 최대공약수 
    return 1;
    
  while(a != b) {   // a, b가 같아질 때까지 큰 수에서 작은 수를 뺀다.
    if(a > b)
      a -= b;
    else
      b -= a;   
  }  
  return a; 
}

 

int main(int argc, char *argv[]) {

  int a = 1, b = 28800000;  
  printf("%d, %d의 최대공약수 = %d %n", a, b, GCD(a, b));
  return 0;
} 

 

 

- 나머지 연산 비교를 이용한 단순 반복으로 GCD 구하기

 

a, b에서 작은수를 구하고 그 숫자를 이용하여 a, b에 나머지 연산을 한다.

나머지 연산이 모두 0인 경우를 찾으면 그것이 최대공약수이다.

만약 하나라도 0이 아닌 경우라면 1씩 줄여가면서 나머지 연산을 시도한다.

이 방식은 앞에서 소개한 방법보다 시간이 오래걸리는 비효율적인 방식이다.

 

int GCD(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 0;
}

 

 

2. 최소공배수(LCM) 

 

유클리드 호제법을 이용하여 최대공약수를 구하면 다음과 같은 공식으로
자연수 a, b의 최소공배수를 쉽게 구할 수 있다.

LCM = (a*b) / GCD(a,b)를 이용해 구해준다..

 

아니면 다음처럼 최소공배수 함수를 만들어 사용해도 된다.

 

// long long 버전

long long LCM(long long a, long long b)
{
   long long x = a;
   long long y = b;
   long long mod = a % b;

   while(mod > 0)  {
     a = b;
     b = mod;
     mod = a % b;
  }
  return (x*y / b); 
}

 

// int 버전

int LCM(int a, int b)
{
   int x = a;
   int y = b;
   int mod = a % b;

   while( mod > 0 )  {
     a = b;
     b = mod;
     mod = a % b;
  }
  return (x*y / b); 
}

<이상>