유클리드 호제법: 최대공약수 구하기
💡 유클리드 호제법이란?
유클리드 호제법 (=유클리드 알고리즘)은 2개의 자연수의 최대공약수를 구하는 알고리즘이다.
a > b인 두 자연수 a, b에 대해서 a를 b로 나눈 나머지, 즉 a % b를 r이라고 했을 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 원리를 이용한 것이다.
이 과정을 계속 반복하여 나머지(r)가 0이 되었을 때, 그 때의 나누는 수(b)가 a와 b의 최대공약수가 된다.
정리하자면,
1. 큰 수를 작은 수로 나눈다. 2. 작은 수를 1에서 나온 나머지로 또 나눈다. 3. 1-2를 나머지가 0이 될 때까지 반복한다. 4. 나머지가 0이 됐을 때 나누는 수가 최대공약수이다.
예시
a = 48, b = 18 이라고 해보자.
그러면 48과 18의 최대공약수는,
18과 12(= 48 % 18 ) 의 최대공약수가 되고,
이는 다시 12와 6(= 18 % 12 ) 의 최대공약수가 된다.
마지막으로 이는 6과 0(= 12 % 6 ), 즉 나머지가 0이 되므로 최대공약수는 6이다.
cf) 최소공배수
참고로 최소공배수는 a * b / (최대공약수) 로 구하면 된다.
코드
유클리드 호제법
// 최대 공약수 구하기: 유클리드 호제법
int divide(int A, int B) {
if (A % B == 0)
return B;
else
return divide(B, A % B);
}ex) BOJ 13241
#include <iostream>
using namespace std;
// 최대 공약수 구하기: 유클리드 호제법
long long divide(long long A, long long B) {
if (A % B == 0)
return B;
else
return divide(B, A % B);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// 입력
long long A, B;
cin >> A >> B;
// 연산 및 출력
long long common;
if (A > B)
common = divide(A, B);
else
common = divide(B, A);
cout << A * B / common;
return 0;
}