[Python] 최대공약수 (GCD)

최대공약수(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이 되었을 때 나누는 수가 x와 y의 최대공약수이다.

1980, 168의 최대공약수 = 24, 12의 최대공약수

 

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 gcd(b, a % b)

 

방법 3. math 라이브러리

import math
math.gcd(a, b)