[알고리즘 잡스] GCD LCM(최대공약수 최소공배수) (C++, 완전 탐색)

문제

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

 

입력

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

 

출력

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

 

---

#include <iostream>

using namespace std;

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

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);
}

두 수가 주어지면 최대공약수(GCD)와 최소공배수(LCM)을 구하는 문제입니다. 최대공약수와 최소공배수를 구하는 문제는 너무 흔합니다. 잘 모르신다면 이번 기회에 코드를 꼭 꼼꼼하게 봐서 로직을 이해하길 바랍니다. 

 

최대공약수는 두 수의 나머지 연산을 사용하여 간단하게 구할 수 있습니다. 나머지 연산을 이용하는 저 방식을 일명 '유클리드 호제법'이라고도 합니다.

 

유클리드 호제법 (출처)

 

1. 입력으로 두 수 m,n(m>n)이 들어온다.
2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
3. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

위 과정은 “n, m에 대해서 나머지 연산을 실시할 수 있다”라는 조건에만 의존하므로, 정수환뿐 아니라, 임의의 유클리드 정역에 대해도 똑같은 과정을 거치면 공약인자가 구해진다. 

 

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

 

 

최소공배수는 앞서 구한 최대공약수를 활용하여 풀 수 있다는 것을 기억하면 다음에 구현할 때 도움이 됩니다.

int lcm(int a, int b) {
	return a * b / gcd(a, b);
}