[algorithm] 최대공약수(GCD)와 최소공배수(LCM) (유클리드 호제법) 최소공배수최소공배수를 구하는 쉬운 방법은 유클리드 호제법을 사용하는 것이다.$$ \text{유클리드 호제법}\\\text{두 자연수 } a, b (a > b)\text{에 대하여}\\a\text{를 } b \text{로 나눈 나머지가 }r \text{일 때}\\a, b \text{의 최대 공약수는 }b, r \text{의 최대 공약수와 같다.}\\\text{즉 } \gcd(a,b) = \gcd(b,r)\\r = 0 \text{의 경우 }a,b \text{의 최대공약수는 }b \text{가 된다.}$$ 계산과정두 수 1568과 1260이 있을 때 두 수중 더 큰 1568을 a 1260을 b로 두고 계산한다.1568 % 1260 = 308, 1260은 나누어 떨어지지 않음 다시 나눔1260 % 308 = 2.. 2025. 2. 14. 이전 1 다음 반응형
