G.C.M. (Greatest Common Measure, 최대공약수 구하기)
- 작성자
- 고친과정
2005년 5월 15일 : 처음씀
1.1. 설명
참고 영상 |
두 정수간의 최대공약수를 구하는 코드입니다. 배보다 배꼽이 더 커진것 같은데 철저한 테스트를 위해서 배꼽이 커졌네요. 이 방법은 '
![[https]](/moniwiki/imgs/https.png)
![[]](/moniwiki/imgs/moni2/external.png)
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 */