최대공약수(gcd)와 최소공배수(lcm) - 파이썬(Python)

1. 기본 성질 이용

# 최대공약수
def gcd(a, b):
  for i in range(min(a,b), 0, -1):
    if a % i == 0 and b % i == 0:
      return i

# 최소공배수
def lcm(a, b):
  for j in range(max(a,b), a*b+1):
    if j % a == 0 and j % b == 0:
      return j

2. math 라이브러리 이용

# 최대공약수 : math.gcd()
import math
def gcd(a, b):
  return math.gcd(a, b)

# 최소공배수 : 두 수의 곱 / 최대공약수
import math
def lcm(a, b):
  return a * b / math.gcd(a, b)

# 최소공배수 : math.lcm은 3.9 이상 버전에서만 가능
import math
def lcm(a, b):
    return math.lcm(a, b)

3. 유클리드 호제법 이용

유클리드 호제법
두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 할 때,
A와 B의 최대공약수는 B와 R의 최대공약수와 같다

# 최대공약수
def gcd(a,b): # 이때 a, b의 대소관계는 상관없다
  if a % b == 0:
    return b
  else:
    return gcd(b, a % b)