|  |  |  |  | ?

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

1.1. 설명

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

두 정수간의 최대공약수를 구하는 코드입니다. 배보다 배꼽이 더 커진것 같은데 철저한 테스트를 위해서 배꼽이 커졌네요. 이 방법은 '[https]유클리드 호제법 (Euclidean algorithm)[]'을 구현한 것입니다.

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 */


Copyright ⓒ MINZKN.COM
All Rights Reserved.