본문 바로가기

알고리즘

재귀로 최대공약수 구하기

Basic 100 · 94번Lv. 1재귀

재귀로 최대공약수 구하기

문제 설명

두 개의 자연수 a와 b가 주어졌을 때, 두 수의 최대공약수를 재귀 함수를 사용하여 구하는 함수를 작성해주세요. 최대공약수는 두 수의 공통된 약수 중에서 가장 큰 수를 의미합니다. 유클리드 호제법으로 풀어 보세요.


제한 사항

  • a와 b는 1 이상 1,000,000 이하의 자연수입니다.
  • 연습 안내: 재귀 함수로 풀어 보세요. 채점은 반환한 결과만 확인합니다.

입출력 예

입력반환값
24, 186
60, 4812
81, 2727
150, 25050
1071, 102921

입출력 설명

  • 첫 번째 예시에서 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24이고, 18의 약수는 1, 2, 3, 6, 9, 18입니다. 두 수의 공통된 약수 중에서 가장 큰 수는 6입니다.
  • 두 번째 예시에서 60의 약수는 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60이고, 48의 약수는 1, 2, 3, 4, 6, 8, 12, 16, 24, 48입니다. 두 수의 공통된 약수 중에서 가장 큰 수는 12입니다.
  • 세 번째 예시에서 81의 약수는 1, 3, 9, 27, 81이고, 27의 약수는 1, 3, 9, 27입니다. 두 수의 공통된 약수 중에서 가장 큰 수는 27입니다.
  • 네 번째 예시에서 150의 약수는 1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 150이고, 250의 약수는 1, 2, 5, 10, 25, 50, 125, 250입니다. 두 수의 공통된 약수 중에서 가장 큰 수는 50입니다.
  • 다섯 번째 예시에서 1071과 1029의 최대공약수는 21입니다.

예시 테스트

#입력기대값
1[24, 18]6
2[60, 48]12
3[81, 27]27

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 7개도 함께 채점해요.