TEAM EDA

최대공약수 구하기 두 자연수 x, y의 최대공약수를 출력하는 프로그램을 작성하세요. 이 문제에서는 유클리드 호제법을 이용하여 두 자연수의 최대공약수를 구합니다. 유클리드 호제법을 간단하게 이야기하면 다음과 같습니다. gcd(x, y) 를 x와 y의 최대공약수라고 정의합니다. 그러면 다음의 식이 성립합니다. gcd(x, y) = gcd(y, x%y) 예를 들어, 1071과 1029의 최대공약수는 따라서 다음과 같이 구할 수 있습니다. gcd(1071, 1029) = gcd(1029, 42) = gcd(42, 21) = 21 참고로 gcd(42, 21) = 21 인 이유는, 42가 21로 나누어 떨어지기 때문에 42와 21의 최대공약수는 21이 됩니다. 자세한 설명은 다음의 링크를 참고해주세요. 위의 예제 ..