[C++] 유클리드 호제법 이용, 최대공약수 최소공배수 구하기

구현을 위한 순서도 작성 

 

 

 

최대공약수 (GCD, Greatest Common Divisor) 구현 함수 int GCD

최소공배수 (LCM, Least Common Multiple) 구현 함수 int LCM

 

#include <iostream>

using namespace std;

int GCD(int a, int b)
{
   if(b==0)
      return a;
   else
      return GCD(b, a%b);
}

int LCM(int a, int b)
{
   return a*b/GCD(a, b);
}

int main()
{
   int numTest;
   cin >> numTest;
   
   for(int i=0; i<numTest; i++)
   {
      int a, b;
      cin >> a >> b;
      cout << GCD(a,b) << " " << LCM(a,b) << endl;
   }
   
   return 0;
}

최대공약수 (GCD)는 재귀함수 return GCD(b, a%b)를 이용하고

최소공배수는 두 수의 곱이 최대공약수와 최소공배수의 곱과 같음을 이용하였다.

a * b = LCM(a,b) * GCD(a,b) 이므로 LCM(a,b) = a * b / GCD(a,b)