[알고리즘] 최대공약수 구하기

최대공약수 구하기

두 자연수 x, y의 최대공약수를 출력하는 프로그램을 작성하세요. 이 문제에서는 유클리드 호제법을 이용하여 두 자연수의 최대공약수를 구합니다. 유클리드 호제법을 간단하게 이야기하면 다음과 같습니다. gcd(x, y) 를 x와 y의 최대공약수라고 정의합니다. 그러면 다음의 식이 성립합니다.

 

gcd(x, y) = gcd(y, x%y)

 

예를 들어, 1071과 1029의 최대공약수는 따라서 다음과 같이 구할 수 있습니다.

 

gcd(1071, 1029) = gcd(1029, 42) = gcd(42, 21) = 21

 

참고로 gcd(42, 21) = 21 인 이유는, 42가 21로 나누어 떨어지기 때문에 42와 21의 최대공약수는 21이 됩니다. 자세한 설명은 다음의 링크를 참고해주세요. 위의 예제 또한 이 링크에서 발췌되었습니다.

입력

첫번째 줄에 두 자연수 x, y가 주어집니다.

출력

두 자연수 x, y의 최대공약수를 출력합니다.

입력 예시

6 4

출력 예시

2

풀이

def GCD(x, y) :
    '''
    x, y의 최대공약수를 반환하는 함수
    '''
    if x % y == 0:
        return y
    else :
        return GCD(y, x%y)


def main():
    '''
    Do not change this code
    '''

    data = input()

    x = int(data.split()[0])
    y = int(data.split()[1])

    print(GCD(x, y))

if __name__ == "__main__":
    main()

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn