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

유클리드 호제법을 이용한 최대공약수와 최소공배수 구하기

 

코드는 어렵게 적어놓았지만 기본 개념은 상당히 간단합니다!

 

두 수를 A와 B라고 했을때

A%B = 0 이라고 했을 때 A는 B의 배수이기 때문에 최대 공약수는 B입니다

 

이런 사실에 대해

A%B가 0이 아닌 C라고 가정했을 때

A와 B의 최대 공약수는 B와 C의 최대공약수와 같다는 원리가 유클리드 호제법입니다.

 

따라서 ? % ? = ? 의 기본식에서 나머지가 0이 될 때까지 값들을 업데이트 해준다면 쉽게 찾을 수 있습니다

 

또한 최소공배수와 최대공약수를 곱한 값은 두 수를 곱한 값과 동일합니다.

#include <iostream>
using namespace std;

//유클리드 호제법을 이용한 최대 공약수 구하기
int gcd(int n1, int n2) {
	int mod_result = n1%n2;
	while (mod_result !=0 ) {
		n1 = n2;
		n2 = mod_result;
		mod_result = n1 % n2;
	}
	return n2;
}

int main() {

	int num1, num2;
	cin >> num1 >> num2;

	//두 수의 최대공약수를 구함
	int gcd_result = gcd(num1, num2);

	//최소공배수는 두수를 곱한값에 최대공약수를 나누면 된다
	cout << gcd_result << '\n' << num1 * num2 / gcd_result;
}