(c++)백준 2609번: 최대공약수와 최소공배수

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

[풀이]

최대 공약수는 아래와 같은 유클리드 호제법으로 풀 수 있다.

60 = 36 * 1 + 24 36 = 24 * 1 + 8 24 = 8 * 3

자연수 A, B의 최소 공배수는 최대 공약수 * 최소 공배수 = A * B임을 이용하여 알 수 있다.

 

#include <iostream>
using namespace std;

//유클리드 호제법
int getGCD(int A, int B) {
	int R;
	while (B != 0) {
		R = A % B;
		A = B;
		B = R;
	}
	return A;
}

//GCD*LCM=A*B
int getLCM(int A, int B, int GCD) {
	return (A*B) / GCD;
}

int main() {
	int A, B;
	cin >> A >> B;

	int gcd = getGCD(A, B);
	int lcm = getLCM(A, B, gcd);

	cout << gcd << '\n' << lcm << '\n';

	return 0;
}