• 두 수의 최대 공약수를 구하는 알고리즘

핵심 이론

• MOD 연산이 최대 공약수를 구하는데 사용되는 핵심 연산

MOD 연산으로 구현하는 유크리드 호제법

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행
2. 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행
3. 단계 2.를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택

• 재귀형태로 구현 가능

[042] 최소 공배수 구하기

• https://www.acmicpc.net/problem/1934
• 최소 공배수 = A * B / 최대 공약수 → 유클리드 호제법
• 따로 정렬해주지 않아도 %연산하면서 작은 수가 b로감

[043] 최대 공약수 구하기

• https://www.acmicpc.net/problem/1850