[백준] [C++] 2609번 최대공약수와 최소공배수

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

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

---

코드

#include <iostream>
using namespace std;

int divisor (int x, int y) {		// 최대공약수
	int z = x % y;

	while (z != 0) {
		x = y;
		y = z;
		z = x % y;
	}
	return y;
}

int multiple(int x, int y) {		// 최소공배수
	return (x * y) / divisor(x, y);
}

int main() {
	int a, b, div, mul;	// div 최대공약수  mul 최소공배수
	cin >> a >> b;

	div = divisor(a, b);
	mul = multiple(a, b);

	cout << div << "\n" << mul;
	
	return 0;
}

---

풀이

두 자연수를 입력받아 최대공약수와 최소공배수를 구하는 문제이다.

 

최대공약수를 구할 때는 '유클리드 호제법'을 사용하면 쉽게 구할 수 있다.

 

• 유클리드 호제법
• a % b = c의 계산을 한다.
• c가 0이 아니라면 b와 c를 다시 나머지 연산을 한다.
• 위 식을 나머지 연산의 값이 0이 될 때까지 반복한다.
• 나머지 연산의 값이 0이 되었을 때 나누는 수의 값이 두 수의 최대공약수이다.

 

최대공약수를 구했다면 최소공배수는 간단한 식을 통해 구할 수 있다.

 

• 최소공배수
• 두 수의 곱 = 최대공약수 * 최소공배수이다.
• 유클리드 호제법을 통해 구한 최대공약수를 통해 최소공배수를 알 수 있다.
• 따라서 최소공배수 = (두 수의 곱) / 최대공약수이다.

 

위 두 공식을 함수로 각각 작성하였다.

 

최대공약수는 divisor 함수를 새로 만들어 유클리드 호제법을 통해 구한다.

 

최소공배수는 multiple 함수를 새로 만드는데 그 안에서 divisor 함수를 사용해 구한다.

 

두 함수를 통해 구한 최대공약수와 최소공배수를 출력한다.