최대 공약수(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.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)