[1934] 최소공배수

---

유클리드 호제법 : 2개의 수의 최대공약수를 구하는 알고리즘

- 호제법 : 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘

 

2개의 자연수 A, B ( A > B )에 대해 A%B = R로 놓는다면 A와 B의 최대공약수는 B와 R의 최대공약수와 같다

A = 24, B = 18이라고 놓았을 때 A%B = 6. 즉 R = 6이다

그 다음 B%R을 반복하여 진행하면 나머지가 0이되는 순간이 온다

그 나누는 수가 A와 B의 최대공약수이다

 

아래는 예시이다

---

유클리드 호제법을 이용하여 최대공약수를 구했으면 최소공배수는 R * (A / R) * (B / R)이다

전체 코드는 아래와 같다

#include <iostream>
using namespace std;

int T, A, B;
int R;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> A >> B;
		int big, small;
		if (A > B) { big = A; small = B; }
		else { big = B; small = A; }
		while (1) {
			R = big % small;
			if (R == 0) {
				R = small;
				break;
			}
			big = small; small = R;
		}
		printf("%d\n", R * (A / R) * (B / R));
	}
}