[백준 BOJ][C++]2609번 최대공약수와 최소공배수 구하기: 유클리드 호제법

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

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

 

 위 문제를 풀기 위해 유클리드 호제법을 사용할 수 있습니다. 

 

• 최대 공약수 구하기

 최대 공약수를 구할 때 유클리드 호제법이 사용되는데, 풀이 과정은 다음과 같습니다. 

 

 (1) 큰 숫자를 작은 숫자로 나눈 나머지

 

 (2) (1)에서 구한 나머지 값으로 작은 숫자 다시 나누기, 그 나머지

 

 (3) 나머지가 0이 될 때까지 위 과정 반복

 

 (4) 나머지가 0일 때 나눈 값이 최대 공약수

 

  

 

• 최소 공배수 구하기

 최대 공약수를 구했다면, 최소 공배수는 쉽게 구할 수 있습니다. 

 

 최대 공약수 * 최대 공배수 = 두 수의 곱

 

 

• 코드

#include<iostream>

using namespace std;

int gcd(int a, int b) { //최대 공약수
	int r = a % b;

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

int lcm(int a, int b) { //최소 공배수
	return (a * b) / gcd(a, b);
}

int main(void) {

	int a, b;

	cin >> a >> b;

	cout << gcd(a, b) << endl;
	cout << lcm(a, b) << endl;

	return 0;
}