10828번

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

프로그램에서 최대공약수를 직접 구하기 위해서는 유클리드 호제법을 이용해야 합니다. ※유클리드 호제법이란 두 수 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..