백준 알고리즘 1934번: 최소공배수 [C++]

문제 출처: www.acmicpc.net/problem/1934

1934번: 최소공배수

1. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	int t;
	cin >> t;

	while (t--)
	{
		int n1, n2, low = 1;	//low = 최대공약수
		cin >> n1 >> n2;

		for (int i = 2; i <= min(n1, n2); i++)
		{
			if (n1 % i == 0 && n2 % i == 0)
				low = i;
		}
		cout << n2 / low * n1 << endl;
	}
	return 0;
}

(실행)

2. 풀이

반복문을 이용하여 간단하게 최대공약수를 구하고 최대공약수의 값을 이용해서 최소공배수를 구하면 된다. 최대공약수와 최대 공배수의 관계는 다음과 같다.

최소공배수 = n1 × (n2 ÷ 최대공약수)

식에 맞게 코드를 작성 후 출력해주면 된다.