Greatest Common Divisor

728x90

1. intro

N/A

최대공약수 즉 GCD를 구하는 문제이다.

이는 유클리드 호제법을 통해 쉽게 구할 수 있으며, 아래 링크와 같이 직접 만들어보았다.

Euclidean algorithm - 유클리드 호제법

서론 크.... 내가 유클리드 호제법에 대해서 포스팅하는 날이 올줄이야... 상상도 못했다 ㅋㅋㅋ 이론 임의의 두 정수가 있을 때 두 정수의 최대공약수를 구하는 방법 중 하나가 유클리드 호제법

wyv3rn.tistory.com

a = int(input())
b = int(input())

while 1:
    if a < b:
        a,b = b,a
    GCD = b
    if (a % b) == 0:
        break
    a = a % b

print(GCD)

┌──(kali㉿kali)-[~/Downloads]
└─$ python GCD.py
66528
52920
1512

728x90