유클리드 호제법1 GCD (최대 공약수) & LCM (최소 공배수) & 유클리드 호제법 📍 GCD : Greatest Common Divisor : 최대 공약수 📍 LCM : Least Common Multiple : 최대 공배수 📌 유클리드 호제법 ? 유클리드 호제법은 두 양의 정수 간의 최대 공약수를 구할 수 있는 방법이다. 단, a 가 b 보다 항상 크다는 전제가 있어야 성립한다. -> 당연한 이야기인게, a = bq + r 공식에서 이미 b는 a의 약수로 속해 있다. a = bq + r 식은 a와 b 간의 관계를 정의한 식이다. -> a가 b 보다 크다면, b*q 값과 어떤 나머지 정수가 더해져 a를 완성할 것이다. 여기서 나머지 값(r) 이 0이게 되면 a와 b 사이에서는 b가 가장 큰 최대 공약수가 되는 것이다 ! 만약 r이 0이 아니라면 ? r은 b와 어떤 정수 q의 곱으로 a.. 2021. 11. 10. 이전 1 다음
