[Algorithm] GCD 최소공약수 알고리즘

예전 블로그에서 GCD에 관한 글을 작성하였는데 너무 오래되어 기억이 안나서 다시 재 작성하기로 했다.

최대공약수, 최소공배수의 개념

• 최대공약수 : 두 수의 약수 중 가장 큰 공통된 약수
• 최소공배수 : 두 수의 배수 중 가장 작은 공통된 배수

유클리드 알고리즘

두 자연수의 최대 공약수(Greatest Common Divisor)를 찾는 알고리즘을 뜻한다.
유클리드 알고리즘으로 푸는 법은 두개가 있다.

첫 번째

• a > b 일 경우 GCD(a,b) = GCD(a-b,b)
• a < b 일 경우 GCD(a,b) = GCD(a, b-a)
• a == b 일 경우 GCD(a,a)=a 이면 최대 공약수이다.

---

재귀함수 구현

int GCD(int a, int b) {
	if (a > b) {
		return GCD(a - b, b);
	}
	if (a < b) {
		return GCD(a, b - a);
	}
	if (a == b) {
		return a;
	}
}

---

반복문 구현

int GCD(int a, int b) {
	while (a != b) {
		if (a > b)
			a = a - b;
		else if (a < b)
			b = b - a;
	}
	return a;
}

---

두 번째 방법

원리

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

• 위키백과

A>B일 때 A%B=r 이고 GCD(A,B) = GCD(B,r) 임을 이용하여 푼다.

A % B = r, B % r = r’ .. 를 반복해 나머지가 0이면 최대공약수이다.

---

반복문 구현

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

---

재귀함수 구현

int GCD(int a, int b) {
	return b == 0 ? a : GCD(b, a % b);
}

최소공배수(LCM) 구현

최소공배수 * 최대공약수 = a * b 임을 이용하여 푼다.

LCM = A * B / GCD(A,B);

---

https://seunghyum.github.io/algorithm/Euclidean-algorithm/#