컴공생의 다이어리

최대공약수(Greatest Common Divisor, GCD) 공약수(common divisor)란 두 수 이상의 여러 수의 공통된 약수를 의미 최대공약수(GCD)란 두 수 이상의 여러 수의 공약수 중 최대인 수를 가리킴 최대공약수가 1이면 두 수는 서로소(coprime) 관계 기본적인 방법 def gcd(a, b): for i in range(min(a, b), 0, -1): if a % i == 0 and b % i == 0: return i 유클리드 호제법 사용 def gcd(a, b): while b > 0: a, b = b, a % b return a # or def gcd(a, b): if a % b == 0: return b elif b == 0: return a else: return g..