두 자연수 a와 b의 최대공약수를 구하는 알고리즘을 만들어 보세요.

 

최대공약수(Greatest Common Divisor, GCD)는 두 개 이상의 정수의 공통 약수 중에서 가장 큰 값을 의미합니다.

문제로 주어진 두 자연수의 최대공약수를 찾으려면 ① 두 수의 약수 중에서 ② 공통된 것을 찾아 ③ 그 값 중 최댓값인 것을 찾아야 합니다. 3단계 중 밑줄 친 약수, 공, 최대라는 단어를 역순으로 읽으면 ‘최대공약수’라는 단어가 만들어집니다.