[백준2609]-최대공약수와 최소공배수(C++)/유클리드 호제법

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

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

유클리드 호제법

유클리드 호제법의 과정은 아래와 같다.

1. 큰 숫자를 작은 숫자로 mod연산을 한다.
2. 작은 숫자를 1번에서 구한 나머지 mod연산을 한다.
3. 위 과정을 mod연산의 결과가 0이 나올때 까지 계속 반복한다.
4. 이때 나누는 수로 사용된 수가 두 수의 최대공약수가 된다.

위 과정을 이용해서 1428과 833의 최대공약수를 구해보도록 하자.

mod연산의 결과가 0이 될때 나누는 수는 119였으니 1428과 833의 최대공약수는 119이다. 이를 코드로 구현하면 아래와 같다.

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

 

최소공배수 구하기

 

최대공약수를 구하기를 완료했다면 최소공배수를 구하는 것은 간단하다. 수학적으로 최대공약수와 최소공배수의 곱은 두 수의 곱과 같기 때문이다.

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

즉 아래와 같이 구할 수 있다.

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

전체 코드

 

위에서 문제가 요구한대로 두 수를 입력받아 최대공약수와 최소공배수를 출력하는 코드는 아래와 같다.

#include <iostream>
using namespace std;

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

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

int main() {
	int n1, n2;
	cin >> n1 >> n2;
	cout << gcd(n1, n2) << "\n" << lcm(n1, n2);
}