[5347] LCM

5347번: LCM

 

최소공약수를 구하는 유클리드 호제법은 할 때마다 까먹기 때문에 가끔 이렇게 복기해줄 필요가 있다고 생각한다.

 

유클리드 호제법

 

 

이때 최대공배수는 a와 b의 곱을 최대 공약수로 나눈 값이다.

 

유클리드 호제법으로 재귀를 이용해 최대 공약수를 구하는 코드는 다음과 같다.

 

#include <iostream>

using namespace std;

int main()
{
    int n;
    
    cin >> n;
    
    while(n--){
        int a, b;
        cin >> a >> b;
        
        int temp = a * b;
        
        while( b != 0 ){
            int temp = b;
            b = a % b;
            a = temp;
        }
        
        cout << temp / a << endl;
    
    }
    
    return 0;
}