유클리드 호제법

유명한 유클리드 호제법은 《원론》 제7권에 나온다. 《원론》은 기원전 300년경 그리스 수학자 유클리드가 썼다. 프톨레마이오스 왕이 《원론》을 훑어보고는 기하학으로 가는 더 짧은 길이 없겠냐고 묻자, 유클리드가 "기하학에 왕도는 없습니다"라고 잘라 말했다는 이야기가 전한다. 《원론》이 열세 권이나 되니 왕이 지름길을 찾은 것도 무리는 아니다. 이 책은 유클리드가 모은 수학 지식과 그가 직접 발견한 내용 일부로 이루어져 있다. 유클리드의 큰 업적은 그 자료를 하나의 유기적인 전체로 아름답게 체계화한 것이다. 《원론》은 이천 년 넘게 표준 교재로 남았다. (Asger Aaboe, Episodes from the Early History of Mathematics 참고)

오늘날의 유클리드 호제법은 보통 이렇게 적는다.

1. $A$와 $B$는 $A > B \geq 0$인 정수다.
2. $B = 0$이면 최대공약수는 $A$이고 알고리즘이 끝난다.
3. 그렇지 않으면 $A = qB + r$이고 $0 \leq r < B$인 $q$와 $r$을 구한다. 이때 $0 \leq r < B < A$이고 $\gcd(A,B) = \gcd(B,r)$이다. $A$를 $B$로, $B$를 $r$로 바꾸고 2단계로 돌아간다.

원래의 유클리드 호제법은 나눗셈 대신 뺄셈을 쓴다. 양의 정수 $A$와 $B$의 공약수는 $\min(A,B)$와 $\max(A,B)-\min(A,B)$의 공약수이기도 하다는 관찰에서 나온다. 그래서 두 양의 정수의 최대공약수를 이렇게 구할 수 있다.

1. $A$와 $B$는 양의 정수다.
2. $A = B$이면 최대공약수는 $B$이고 알고리즘이 끝난다.
3. 그렇지 않으면 $A$를 $\max(A,B)-\min(A,B)$로, $B$를 $\min(A,B)$로 바꾸고 2단계로 돌아간다.

$A = 24$, $B = 15$에서 출발하면 원래의 호제법은 다음 순서로 진행한다.

1. $A = 24-15 = 9$, $B = 15$
2. $A = 15-9 = 6$, $B = 9$
3. $A = 9-6 = 3$, $B = 6$
4. $A = 6-3 = 3$, $B = 3$

즉 $\gcd(24,15) = 3$을 얻기까지 3단계를 네 번 실행한다.

두 양의 정수가 주어질 때, 원래의 유클리드 호제법이 3단계를 몇 번 실행하는지 구하라.

첫째 줄에 양의 정수 두 개가 공백 하나 이상으로 구분되어 주어진다. 두 정수 모두 32767보다 크지 않다.

첫째 줄에 원래의 유클리드 호제법이 3단계를 실행하는 횟수를 출력한다.