| 검색 | ?

G.C.M. (Greatest Common Measure, 최대공약수 구하기)

1.1. 설명

최대 공약수는 두 수 이상의 수에 대한 공약수(공통된 약수) 중에서 가장 큰 수를 가리킵니다. GCM(Greatest Common Measure) 또는 GCD(Greatest Common Divisor)이라고 표기하기도 합니다.

이 방법은 '[https]유클리드 호제법 (互除法, Euclidean algorithm)[]'을 응용하여 두 정수간의 최대공약수를 구하는 코드구현입니다.
  • 두 양의 정수 a와 b (단, a > b 일 때)에 대하여 a = bq + r (단, 0 ≤ r ≤ b) 또는 a ≡ r (r은 a mod b) 이라 하면, a와 b의 최대공약수 b와 r의 최대공약수와 같다.
    • 즉, gcd(a, b) = gcd(b, r) 에서 r 이 0이라면, a와 b의 최대공약수는 b가 된다.
  • 여기서 '호제법'이라는 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘(algorithm)을 의미합니다.
  • 간단히 이것을 C언어 함수로 핵심적인 요점만 구현한다면 다음과 같은 구현을 의미합니다. 
    int EuclideanAlgoriithmType1(int a, int b)
{
    /* COND1: 'a > b' */
    /* COND2: '0 ≤ r ≤ b' */
    int r = a % b; /* r = a mod b */

    /* r 이 0이라면, a와 b의 최대공약수는 b */
    /* 'gcd(a, b) == gcd(b, r)' */
    return (r == 0) ? b : EuclideanAlgoriithmType1(b, r);
}

또는

int EuclideanAlgoriithmType2(int a, int b)
{
	return b ? EuclideanAlgoriithmType2(b, a % b) : a;
}

또는

int EuclideanAlgoriithmType3(int a, int b)
{
    int r;

    while (b) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

1.2. 사용방법

gcm.c 로 소스를 저장후 컴파일은 요렇게 합니다. 
bash# gcc -o gcm gcm.c

1.3. 코드

/* 
  Copyright (C) JAEHYUK CHO
  All rights reserved.
  Code by JaeHyuk Cho <mailto:minzkn@minzkn.com>
*/ 

#include <stdio.h> 

#if 0 
typedef unsigned int t_gcm_value; 
#else 
typedef int t_gcm_value; 
#endif 

static t_gcm_value _gcm_to_abs(t_gcm_value s_value) 
{ 
 static t_gcm_value sg_msb = (((t_gcm_value)1) << ((sizeof(t_gcm_value) << 3) - 1)); 
 t_gcm_value s_temp; 
 s_temp = sg_msb >> ((sizeof(t_gcm_value) << 3) - 1); 
 if(s_temp != ((t_gcm_value)1)) 
 { /* t_gcm_value is signed type */ 
  if((s_value & sg_msb) == sg_msb) 
  { /* s_value < 0 */ 
   s_value = -s_value; 
  } 
 } 
 return(s_value); 
} 

static t_gcm_value _gcm(t_gcm_value s_value1, t_gcm_value s_value2) 
{ 
 t_gcm_value s_temp; 
 if(s_value1 < s_value2) 
 { /* swap */ 
  s_temp = s_value1; 
  s_value1 = s_value2; 
  s_value2 = s_temp; 
 } 
 do 
 { 
  s_temp = s_value1 % s_value2; 
  if(s_temp == ((t_gcm_value)0))break; 
  s_value1 = s_value2; 
  s_value2 = s_temp; 
 }while(1); 
 return(_gcm_to_abs(s_value2)); 
} 

void gcm(t_gcm_value s_value1, t_gcm_value s_value2) 
{ 
 t_gcm_value s_value; 
 s_value = _gcm(s_value1, s_value2); 
 (void)fprintf(stdout, "gcm(%ld, %ld) = %ld\n", 
  (long)s_value1, (long)s_value2, (long)s_value); 
} 

int main(void) 
{ 
 /* test suite */ 
    
 gcm(8, 12); 
 gcm(12, 8); 
 gcm(12, 18); 
 gcm(3, 2); 
 gcm(100, 200); 
 gcm(300, 124); 

 (void)fprintf(stdout, "\n"); 
  
 gcm(-8, -12); 
 gcm(-12, -8); 
 gcm(-12, -18); 
 gcm(-3, -2); 
 gcm(-100, -200); 
 gcm(-300, -124); 
  
 (void)fprintf(stdout, "\n"); 
  
 gcm(-8, 12); 
 gcm(-12, 8); 
 gcm(-12, 18); 
 gcm(-3, 2); 
 gcm(-100, 200); 
 gcm(-300, 124); 
  
 (void)fprintf(stdout, "\n"); 
  
 gcm(8, -12); 
 gcm(12, -8); 
 gcm(12, -18); 
 gcm(3, -2); 
 gcm(100, -200); 
 gcm(300, -124); 
  
 (void)fprintf(stdout, "\n"); 
  
 gcm(0xffffffff, 0xffffffff); 

 return(0); 
} 

/* End of source */

1.4. 참고자료

[백점맞는수학] 초등5학년_공약수와최대공약수
참고 영상

[재미있는수학 Funny Math] 최대공약수 구할때 소인수분해 하지마세요 (재미있는 수학 유클리드 호제법)
참고 영상

Copyright ⓒ MINZKN.COM
All Rights Reserved.