[BAEKJOON C++] 2609_최대공약수와 최소공배수

 최대공약수와 최소공배수의 곱은 두 수의 곱과 같음

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

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

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

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

/*
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램

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

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

// 표준 스트림에서 읽기 및 쓰기를 제어하는 개체를 선언
#include <iostream>
using namespace std;

// 최대 공약수
int gcd(int a, int b) {
	// (1) 큰 숫자를 작은 숫자로 나눈 나머지
	int r = a % b;

	// (3) 나머지가 0이 될 때까지 위 과정 반복
	// (4) 나머지가 0일 때 나눈 값이 최대 공약수
	while (r != 0) {
		a = b;
		b = r;
		// (2) (1)에서 구한 나머지 값으로 작은 숫자 다시 나누기, 그 나머지
		r = a % b;
	}
	return b;
}

// 최소 공배수
int lcm(int a, int b) {
	//  최대 공약수 * 최대 공배수 = 두 수의 곱
	return (a * b) / gcd(a, b);
}

int main()
{	
	int a, b;
	cin >> a >> b;
	cout << gcd(a, b) << endl;
	cout << lcm(a, b) << endl;
	return 0;
}