[Bronze / 2609] 최대공약수와 최소공배수

문제 링크

---

🔷 분류

수학, 정수론, 유클리드 호제법

✒️ 문제 설명

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

⬅️ 입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

➡️ 출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

💻 코드 (C++)

#include <iostream>
using namespace std;

int GCD(int a, int b) {
	int r;
	r = a % b;
	if(r == 0) return b;
	else return GCD(b, r);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int a, b;
	cin >> a >> b;
	int g;
	if (a > b) g = GCD(a, b);
	else g = GCD(b, a);
	int l = (a * b) / g;
	cout << g << "\n" << l;
	
	return 0;
}