욤미의 개발일지

최대공약수(Greatest Common Divisor, GCD) 최대공약수란 두 수 이상의 여러 수의 공약수 중 최대인 수를 의미 최대공약수가 1이면 두 수는 서로소(coprime) 관계 방법 1 def gcd(a, b): for i in range(min(a, b), 0, -1): if a % i == 0 and b % i == 0: return i 방법 2. 유클리드 호제법 x, y의 최대 공약수 = y, r의 최대 공약수 (x%y=r) 2개의 자연수 x, y에 대해서 x를 y로 나눈 나머지를 r이라 하면(단, x>y) x와 y의 최대공약수는 y와 r의 최대공약수와 같다. 이에 따라, y를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 ..