문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

풀이

해당 문제는 유클리드 호제법을 이용하여 푸는 문제이다.
유클리드 호제법은 최대공약수를 구하는 알고리즘 중 하나로, 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 것을 나타낸다.

유클리드 호제법?

자연수 a, b와 a를 b로 나눈 나머지를 r이라 하자. (이때, a>b)
a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

이렇게 최대 공약수를 구했으면, 최소 공배수를 구하는 것은 간단하다.
(최대 공약수) * (최소 공배수) = (두 수의 곱) 이기 때문이다.

코드

using namespace std;
#include <iostream>

int gcd(int a, int b) { //최대 공약수
	int r = a % b;

	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int lcm(int a, int b) { //최소 공배수
	return (a * b) / gcd(a, b);
}

int main(void) {

	int a, b;

	cin >> a >> b;

	cout << gcd(a, b) << endl;
	cout << lcm(a, b) << endl;

	return 0;
}