파이썬] 최대 공약수를 구하기(GCD)

최대 공약수(Greatest Common Divisor, GCD)는 두 개 이상의 정수의 공통 약수 중에서 가장 큰 값을 의미

 

최대 공약수 구하기

def gcd(a,b):
    i = min(a, b)   # 두 수 중에서 최솟값을 구하는 파이썬 함수
    while True:
        if a % i == 0 and b % i == 0:
            return i
        i = i - 1   # i를 1만큼 감소 시킴
    
print(gcd(1, 5))    #1
print(gcd(3, 6))    #3
print(gcd(60, 24))  #12
print(gcd(81, 27))  #27

a % == 0 에서 %는 나머지를 구하는 연산자. 즉, a를 i로 나누었을 떄 나머지가 0이면 a는 1로 나누어떨어진다는 의미

def gcd(a,b):
    if  b == 0:      # 종료조건
       return a
    return gcd(b, a%b) # 좀 더 작은 값으로 자기 자신을 호출
    
print(gcd(1, 5))    #1
print(gcd(3, 6))    #3
print(gcd(60, 24))  #12
print(gcd(81, 27))  #27