유클리드 호제법

정의

유클리드 호제법(유클리드 알고리즘)은 최대공약수 (GCD : Greatest Common Divisor)를 구하는 알고리즘이다. 다른 두 수를 각각 A, B (단 A > B), A를 B로 나눈 나머지를 r 이라고 가정할때 A와 B의 최대공약수는 B와 r의 최대 공약수와 같다. 

 

즉 GCD(A,B) = GCD(B,r) = GCD(A, A%B)

코드

반복문 구현

int gcd(int a, int b) {
	int tmp;

	while (b > 0) {
		tmp = a % b;
		a = b;
		b = tmp;
	}
	return tmp;
}

재귀 구현

int gcd(long long int a, long long int b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}

활용

두 수 a, b가 있을때, 최대공약수 = G 최소 공배수 = L 이라고 하면 a * b = G * L 이 성립한다,

따라서 두 수의 최대공약수를 두하면 최소공배수를 구할 수 있다.

L = a * b / G

 

따라서 최대 공약수를 알면 최소 공배수를 구할 수 있게 된다.

 

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

13241번: 최소공배수