정수에 대한 유클리드 호제법
a >= b이고 a를 b로 나눈 나머지를 r 이라고 하자 유클리드 호제법의 가장 핵심은 다음과 같다. a, b의 최대공약수를 (a, b) b, r의 최대공약수를 (b ,r) 이라고 하면 (a, b) = (b, r) 이 성립한다. 예를 들어, (48, 18) = (18, 12) = (12 , 6) = (6, 0) = 6 처럼 쓸 수 있다. 즉 , 뒤의 자리가 0이 될 때 까지 연산을 진행한다. 만약 두 수가 서로소라면 (17, 13) = (13, 4) = (4, 1) = (1, 0) = 1 다음과 같이 나타남을 알 수 있다. 서로소 또한 결과가 잘 나타남을 알 수 있다. 이제 유클리드 호제법을 코드로 나타내면 다음과 같다. def gcd(m, n): if m < n : m,n = n, m if n == 0..
2021. 9. 7.
