[C++] 최대 공약수, 최소 공배수 함수 직접 만들기

<a href="https://www.flaticon.com/free-icons/c-" title="c++ icons">C++ icons created by Freepik - Flaticon</a>

프로그램에서 최대공약수를 직접 구하기 위해서는 유클리드 호제법을 이용해야 합니다.

※유클리드 호제법이란

두 수 A와 B의 최대 공약수를 구하기 위해서는 유클리드 호제법을 이용해 몫과 나머지를 이용하여야 합니다.
두 수가 최대 공약수 G를 가질 때 A와 B는 A=Ga / B=Gb 로 나타낼 수 있습니다.

또한, A를 B로 나눌 때 A = B * Q + R 이라는 식을 도출할 수 있습니다.
이 식은 Ga=GbQ+R과 Ga-GbQ=R ..... G(a-bQ)=R 로 바뀌며 나머지는 G라는 최대 공약수를 가짐을 보입니다. 

따라서 A를 B로 나눌 때의 나머지도 같은 최대공약수를 가짐을 이용하여
나머지가 0이 될때까지 연산을 수행합니다.

 

먼저 최대공약수를 구하는 checkmin 함수 입니다.

int checkmin(int a, int b) {
	if (!b) return a;
	else return checkmin(b, a % b);
}

먼저 a가 b보다 크다고 가정했으므로 변수 b로 들어오는 수가 0이 될 때까지 재귀함수를 호출하다

b가 0이 될때 그때의 제수를 리턴시켜주는 함수입니다.

 

이때 재귀함수를 호출할 시 인자값은 이전의 나누어주었던 제수와 나머지가 들어갑니다.

---

최대공약수까지 구한다면 최소공배수를 구하는 법은 어렵지 않은데요

 

A와 B가 A=Ga / B=Gb 로 나타낼 수 있고 a와 b는 서로소 이므로 최소공배수는 abG로 나타낼 수 있습니다.