hahahia

유클리드 호제법을 이용한 GCD, LCM 프로그램 본문

Algorithm

유클리드 호제법을 이용한 GCD, LCM 프로그램

hahahia 2011. 5. 22. 10:38

#include <stdio.h>

int u_gcd(int, int);
int u_lcm(int, int, int);
int main()
{
 int a, b, gcd, lcm;
 printf("두 수를 입력하세요 : ");
 scanf("%d %d", &a, &b);
 gcd = u_gcd(a, b);
 printf("두 수의 최대공약수는 %d입니다.\n", gcd);
 lcm = u_lcm(a, b, gcd);
 printf("두 수의 최소공배수는 %d입니다.\n", lcm);
 return 0;
}
int u_gcd(int x, int y)
{
 if(x==y)
 {
  return x;
 }
 else if(x > y)
 {
  return u_gcd(x-y, y);
 }
 else
 {
  return u_gcd(x, y-x);
 }
}
int u_lcm(int x, int y, int Gcd)
{
 return x * y/ Gcd;
}

'Algorithm' 카테고리의 다른 글

더블릿 문제풀이(최대 구간 구하기)  (0) 2012.10.04
쉬프트 연산( << , >> )  (0) 2012.09.01
Selection Sort(선택 정렬)  (2) 2012.04.06
merge sort(병합 정렬)  (0) 2012.03.23
insertion sort(삽입정렬)  (0) 2011.06.05
Comments