알고리즘/이론
유클리드 호제법(Euclidean Algorithm)
엠씨비기
2017. 6. 25. 19:44
유클리드 호제법이란?
2개 정수의 최대공약수를 구하는 방법 중 하나입니다.
2개의 정수 a, b (a>b) 에 대하여 a를 b로 나눈 나머지를 r이라 할때,
a와 b의 최대공약수는 b와 r의 최대공약수와 같음을 활용합니다.
이 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수 입니다.
유클리드 호제법 구현
int a, b;
int gcd(int a, int b)
{
if (b > a) swap(a, b);
int r = a % b;
if (r == 0) return b;
else return gcd(b,r);
}
유클리드 호제법 예제
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int a, b;
//유클리드 호제법을 활용한 최대공약수 계산
int gcd(int a, int b)
{
if (b > a) swap(a, b);
int r = a % b;
if (r == 0) return b;
else return gcd(b, r);
}
int main(int argc, char* argv[])
{
scanf("%d %d", &a, &b);
int ab_gcd = gcd(a, b);
//두 수의 곱은 최대공약수와 최소공배수의 곱과 같다(정수론)
int ab_lcm = a * b / ab_gcd;
printf("%d\n", ab_gcd);
printf("%d\n", ab_lcm);
return 0;
}