최대공약수(greatest common divisor(factor), GCD), 최소공배수(least common multiple, LCM)를 구하는 방법에 대해 알아보자. 최대공약수, 최소공배수란? 최대공약수(GCD) : 두 수 혹은 여러 수의 공통인 약수 중 가장 큰 것 최소공배수(LCM) : 두 수 혹은 여러 수의 공통인 배수 중 가장 작은 것 최대공약수, 최소공배수 구하기 최대공약수를 구하는 방법에는 다음과 같이 계속 나누는 방법도 있다. ex. 2 | 72 56 2 | 36 28 2 | 18 14 ----- 9 7 따라서 72와 56의 최대공약수는 2*2*2 = 8이므로 8이고, 최소공배수는 2*2*2*9*7 = 504이므로 504이다. 하지만 이런 방법의 시간 복잡도는 O(N)이므로 시간복잡도..
