python 최대공약수 구하는 함수

"프로그래머스 입문 분수의 덧셈"
두 분수가 주어질때, 두 분수를 더한 값을 기약분수로 나타내려면?
-> 최대공약수를 구해야 한다.

최대공약수 : 공통의 약수중에서 가장 큰 것

def gcd(a,b):
	i = min(a,b)
    while True:
    if a% i == 0 and b % i == 0:
    	return i
	i = i - 1
    

def gcd(a,b):
	for i in range(min(a,b), 0, -1):
    	if a % i == 0 and b % i == 0:
        	return i

유클리드 호제법 !!
: x,y의 최대공약수는 y,r(x%y값)의 최대공약수와 같다는 원리를 이용한다.

• 계속 왼쪽 이동시켜서 값이 0이나오면 y값이 최대공약수라는 뜻.
  x%y == r
  y%r == r'
  r%r' == 0
  이때 r'가 최대공약수라는 뜻!

def GCD(x,y):
	while(y): # y가 0이 되기 전까지 돌리겠다.
    	x,y = y,x%y
    return x