알고리즘 | 유클리드 알고리즘(최대공약수)

유클리드 알고리즘 (최대공약수) 최대 공약수A = aG; (280 = 2810)B = bG; (30 = 310) A-B = aG - bG = (a-b) * G(a-b) 와 b는 역시 서로소 이므로 A-B와 B의 최대 공약수는 역시 G [뺄셈 이용] -> 성능 최악 임의의 두 정수 u와 v를 입력 받는다 v가 u보다 크다면 v와 u의 값을 교환한다 u