Python 최대 공약수, 최소 공배수

📚 최대 공약수

유클리드 호제법

• 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지와 B의 최대 공약수는 A와 B의 최대 공약수와 같다.

  def gcd(a, b):
  if a % b == 0:
    return b
  else:
    return gcd(b, a % b)
  

📚 최소 공배수

구현

• 서로 다른 a, b의 곱을 a, b의 최대 공약수로 나눈다.

  def lcm(a, b):
  return a * b / gcd(a,b)
  

📚 math

라이브러리를 사용하여 구하기

import math
# 최대 공약수
print(math.gcd(6, 9))
# 최소 공배수
print(math.lcm(2, 3))