GCD / LCM

최대 공약수 / 최소 공배수

개념

• 약수: 어떤 수를 나누어떨어지게 하는 수
• 배수: 어떤 수의 1, 2, 3, …n 배하여 얻는 수
• 공약수: 둘 이상의 수의 공통인 약수
• 공배수: 둘 이상의 수의 공통인 배수
• 최대 공약수(GCD. Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수
• 최소 공배수(LCM. Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수

유클리드 호제법

1. a,b 를 서로를 나눈다. 만약 나누어진다면 b가 최대공약수이다.(a > b이다.)
2. 만약 서로가 나누어지지 않는다면 b와 a % b(a를 b로 나눈 나머지) 다시 나눈다.
3. 서로가 나누어진다면 a % b가 최대공약수이다. 만약 나누어지지 않는다면 다시 위 방법을 반복한다.