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

이 방법은 '유클리드 호제법 (互除法, 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;
  }
  

gcm.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학년_공약수와최대공약수

참고 영상

[Youtube movie]

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

참고 영상

[Youtube movie]