최대공약수 ➡️유클리드 호제: 2 개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다 두 수를 입력으로 받고 작은 수가 0이 될때 까지 나누기 def gcd(a, b): while (b != 0): r = a % b a = b b = r return a 최소공배수 두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다. def lcm(a, b): return (a * b) / gcd(a, b) def gcd(a, b): while (b != 0): r = a % b a = b b = r return a