유클리드 호제법(Euclidean Algorithm)

유클리드 호제법이란 최대공약수(greatest common divisor)를 구하는 알고리즘이다.
호제법이라는 말은 서로 나누기 때문에 붙여진 이름이다.

과정

1. 두 수 중 큰 수를 작은 수로 나눈다.
2. 나머지가 0이면 작은 수가 최대공약수가 된다.
3. 나머지가 0이 아니면 작은 수가 큰 수가 되고, 나머지를 작은 수로 대체하고 반복한다.

코드