호제법
-
유클리드 호제법Algorithms 2017. 11. 9. 10:55
오늘은 최대 공약수를 구할 수 있는 파워풀한 알고리즘인유클리드 호제법 에 대해 포스팅을 하도록 하겠다. 유클리드 호제법의 정의는 다음과 같다. 두 양의 정수 a, b (b > a) 에 대해 b = aq + r (0 35 이므로 r = 35 이다.즉, gcd(60, 95) = gcd(60, 35) = gcd(35, 60) 이다.다음 식은60 % 35 -> 25 이므로gcd(35, 60) = gcd(35, 25) = gcd(25, 35) 이고,35 % 25 -> 10 이므로gcd(25, 35) = gcd(25, 10) = gcd(10, 25) 이고...25 % 10 -> 5 이므로gcd(10, 25) = gcd(10, 5) = gcd(5, 10) 이고10 % 5 -> 0 이므로최대 공약수는 5 가 된다. 요..