최대공약수 최대공약수(gcd, greatest common divisor)란? 0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수이다. 따라서 두 정수 a와 b의 최대공약수는 a의 약수인 동시에 b의 약수인 수, 즉 두 정수 a, b의 공약수 중에서 가장 큰 수를 의미한다. 약수와 최대공약수 두 정수 a = 12와 b = 30의 최대공약수를 구해보자. 12의 약수는 1, 2, 3, 4, 6, 12 이고, 30의 약수는 1, 2, 3, 5, 6, 10, 15, 30 이다. 따라서 12와 30의 공약수는 1, 2, 3, 6 이고, 공약수 중 가장 큰 수는 6이므로 두 수 12와 30의 최대공약수는 gcd(12, 30) = 6 이다. 파이썬에는 math 라이브러리에 최대공약수를 반환해주는 gcd..