본문 바로가기

최대 공약수1

최대 공약수와 최소 공배수 알고리즘 유클리드 호제법은 두 수의 최대 공약수는 큰 수에서 작은 수를 빼가며 어느 한 쪽이 0일때까지 반복하여 마지막에 0이 아닌 다른 한 수임을 이용하는 방법입니다. 예를 들어 gcd(7,15) -> gcd(7,8) -> gcd(7,1) -> gcd(6,1) -> gcd(5,1) -> gcd(4,1) -> gcd(3,1) -> gcd(2,1) -> gcd(1,1) -> gcd(0,1) gcd(6,8) -> gcd(6,2) -> gcd(4,2) -> gcd(2,2) -> gcd(0,2) 와 같이 진행하며 7과 15의 최대 공약수가 1, 6과 8의 최대 공약수가 2임을 알 수 있습니다. max(a,b) - min(a,b) 연산은 max(a,b) % min(a,b) 연산으로 대체 할 수 있으므로 아래와 같이 정리 .. 2020. 8. 9.

티스토리툴바