[백준 1934 / C++] 최소공배수

해당 문제에서는 

1. 최대공약수 구하기 - 유클리드 호제법
2. 최대공약수를 이용해서 최소공배수 구하기 - 수가 2개일 경우.

가 필요하다.

유클리드 호제법 -  최대공약수 구하기
(유클리드 호제법 같은 공식은 외워두는 게 유용할 것 같기에 따로 정리하기로 하였다.)

정수(a,b)가 있고 a,b의 최소공배수를 구할 때,
a = b * ? ...c
b = c * ? ...d
c = d * ? ...e

이런식으로 반복되고 나머지가 0이 되면 그걸 나눈 값이 최대공약수가 된다.

EX1)
(6,2)
6 = 2 * 3 ...0        -> 나머지가 0이기에 2가 최대공약수이다.

EX2)
(17,13)
17 = 13 * 1 ...4
13 = 4 * 3 ...1
4 = 1 * 4 ...0         -> 나머지가 0 이기에 1이 최대공약수이다.

최대공약수를 이용해서 최소공배수를 구하는 법
이건 수가 몇 개인지에 따라 다르다.
즉 2개의 수의 최소공배수를 구하느냐, 3개 수의 최소공배수를 구하느냐에 따라 다름.

2개 수일 경우)
두 자연수의 곱 = 최소공배수 * 최대공약수 
최소공배수 = 최대공약수/두 자연수의 곱

#include <iostream>
using namespace std;

int gcd(int a, int b) {
	int c;
	while (b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

int main() {
	int T; //테스트 케이스의 개수
	int A, B; //입력받을 자연수 A,B
	int least_common_multiple; //자연수 A,B의 최소공배수
	//int greatest_common_divisor; //자연수 A,B의 최대공약수
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> A >>  B;

		int max = (A < B) ? B : A;
		int min = (A < B) ? A : B;

		int greatest_common_divisor = gcd(max, min);
		least_common_multiple = (A * B) / greatest_common_divisor;

		cout << least_common_multiple << endl;
	}


	return 0;
}