최대공약수, 최소공배수 알고리즘 유클리드 호제법으로 최대공약수 구하기최대공약수를 구하는 함수를 라고 하자. 이라면, 임이 성립. 이 이라면, 임이 성립한다.def gcd(a, b): mod = a%b while mod > 0: a = b b = mod mod = a%b return b 최소공배수최소공배수는 a과 b의 곱에 최대공약수를 나누어 준 것과 같다.def lcm(a, b): return a*b//gcd(a,b) 최대공약수 (GCD : Greatest Common Divisor)최소공배수 (LCM : Least Common Multiple)