[C++] 유클리드 호제법으로 최대공약수, 최소공배수 구하기

안녕하세요. 오늘은 C++에서 최대공약수와 최소공배수를 구해보겠습니다.

 

C++에서 사용하는 정형적인 최대공약수 알고리즘은 유클리드 호제법이 있는데요.

호제법은 공약수를 구하는 알고리즘이라는 뜻이에요.

 

오늘은 유클리드 호제법을 자세하게 분석하기 보다는 동작을 살펴보면서 코드로 옮기는 것만 설명해볼건데요.

암호학에서는 자주 사용하는 알고리즘이니 관심이 있으시다면 찾아보는 것도 괜찮을 것 같습니다.

---

최대공약수

최대공약수는 정수들의 공통적인 약수 중에서 가장 큰 놈을 말합니다.

https://ko.wikipedia.org/wiki/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98

최대공약수 - 위키백과, 우리 모두의 백과사전

 

 

유클리드 호제법은 설명만 들었을 때는 살짝 아리송한데,

막상 코드는 그렇게 길지는 않아서 외워두면 좋을 것 같습니다.

 

우선 그림으로 먼저 보겠습니다.

아래 그림에서 a는 4고 b는 6이에요.

이때 4는 6보다 작기 때문에 a를 b로 나누면 몫이 0이고 나머지가 4죠. 나머지 4를 잘 기억해두세요.

다음엔 b를 a로 밀어내고 b에 나머지 4를 넣어주겠습니다.

이번에도 마찬가지로 a를 b로 나눠줍니다. 몫은 1, 나머지는 2가 되겠네요.

나눠진 만큼 a에서 제해줄게요.

그리고 아까처럼 b를 a로, 나머지를 b로 바꿔줍니다.

이제 감히 잡히신 분도 있을 것 같습니다.

이 패턴을 반복하다 보면 결국 a와 b는 2와 0이 됩니다.

최대공약수는 0이 아닌 수이니 4와 6의 최대공약수는 2가 되겠네요.

 

아래는 이 과정을 C++로 옮긴 코드.

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

	return a;
}

 

---

최소공배수

최소공배수는 양의 공배수 중 가장 작은 놈을 말합니다.

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

최소공배수 - 위키백과, 우리 모두의 백과사전

 

최대공약수를 알아냈다면 최소공배수는 간단합니다.

최대공약수와 최소공배수에는 다음과 같은 식이 성립하는데요.

a * b = gcd(a, b) * lcm(a, b)

 

여기서 gcd는 최대공약수, lcm은 최소공배수를 뜻합니다.

우리는 a, b 그리고 gcd(a, b)를 알고 있으니 최소공배수인 lcm(a, b)를 구할 수 있겠네요.

 

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

 

 

도움이 되셨다면 하트와 댓글 부탁드립니다.