본문 바로가기

Studies/A Structured Approach Using C++

Project 9-67 Euclid's method to get the Greate commom divisor and the Least common muliple 유클리드 소거법으로 최대공약수, 최소공배수 구하기

//============================================================================
//  제출일 : 2005. 4. 12
//  작업환경 :  Windows XP SP1, VC++ 6.0, Pentium4
//  연습문제 9-67
//============================================================================

#include <iostream.h>

int get_gcd(int a, int b); //recursive fuction

int main()
{
 int gcd;
 int a, b;

 cout << "input factor A : ";
 cin >> a;
 cout << "input factor B : ";
 cin >> b;

 gcd = get_gcd(a, b);
 cout << "gcd is " << gcd << endl;
 cout << "lcm is " << a*b/gcd << endl;

 return 0;
}

int get_gcd(int a, int b) //get gcd by recursive
{
 if (a ==0 || b == 0)
  return a+b;
 else if (a >= b)
  return get_gcd(a%b, b);
 else
  return get_gcd(b%a, a);
};