#keywords 최대공약수,GCM,Greatest,Common,Measure,Divisor,약수,공약수,유클리드,호제법,mod
#title G.C.M. (Greatest Common Measure, 최대공약수 구하기)
[wiki:Home 대문] / [wiki:CategoryBasic 기초지식], [wiki:CategoryProgramming 프로그래밍] / [wiki:GCM G.C.M. (Greatest Common Measure, 최대공약수 구하기)]
----
== [wiki:GCM G.C.M. (Greatest Common Measure, 최대공약수 구하기)] ==
 * 작성자
  조재혁([mailto:minzkn@minzkn.com])

 * 고친과정
  2005년 5월 15일 : 처음씀

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

 이 방법은 '[^https://en.wikipedia.org/wiki/Euclidean_algorithm 유클리드 호제법 (互除法, 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언어 함수로 핵심적인 요점만 구현한다면 다음과 같은 구현을 의미합니다.
   {{{#!enscript 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;
}
}}}
=== 사용방법 ===
 gcm.c 로 소스를 저장후 컴파일은 요렇게 합니다.
  {{{#!plain
bash# gcc -o gcm gcm.c
}}}
=== 코드 ===
 {{{#!enscript c
/* 
  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 */
}}}
=== 참고자료 ===
 |[백점맞는수학] 초등5학년_공약수와최대공약수|  참고 영상  ||
 ||  [[Play(https://youtu.be/8771Hg5Z1Yk)]]  ||

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