최대공약수 (Greatest Common Divisor - GCD) 두 수의 공약수 중 가장 큰 수를 뜻한다. 최소공배수 (Least Common Multiple - LCM) 두 수의 공배수 중 가장 작은 수를 의미한다. lcm = 두 수의 곱 / gcd로 구할 수 있다. 유클리드 호제법 두 양의 정수의 최대공약수를 구하는 방법이다. 두 양의 정수 a, b(a > b)에 대하여 a = bq + r일 때 a와 b의 최대공약수는 b, r의 최대공약수와 같다. r = 0이라면, a, b의 최대공약수는 b가 된다. 이를 파이썬으로 구현해보면 다음과 같다. def Euclidean(a, b): while b != 0: r = a % b a = b b = r return a 내부 과정을 확인해보면 아래와 같다. d..