[C++]최대공약수, 최소공배수 구하기

간혹 프로그래밍 기본 문제로 최대공약수와 최소공배수를 구하는 문제가 나옵니다.

이번 글에서는 위 문제에 대한 다양한 해결 방법이 존재하겠지만

유클리드 호제법을 이용하여 해결하는 방법을 적어두겠습니다.

A. 최대공약수

유클리드 호제법은 두 수를 입력받았을 때,

1. 큰 수에서 작은 수를 나눈 나머지를 구한다.

2. (1)에서의 과정에 작은 수를 다시 한번 큰수로 입력, 나머지를 작은 수로 입력하여 (1)의 과정을 계속 반복한다.

3. 나머지가 0이 되면 (2)까지의 과정을 종료한다.

4. 마지막으로 나눈 값이 최대공약수이다.

B. 최소공배수

최소 공배수를 구하는 방법은 위에서 구한 최대 공약수로 처음의 큰 수와 작은 수의 곱을 나누면 된다.

식 : 큰 수 * 작은 수 / 최대 공약수