🗂️ 2024.08.09 TIL

Python

최소공배수를 구하는 문제

알고리즘 문제들을 풀다보면 최소공배수, 최대공약수를 구하는 문제가 꽤 나오는거 같다. 그래서 한번 더 정리해서 다음번에 해당 문제가 나오면 반가운 느낌이 들었으면 한다.

최대공약수: 두 수가 서로 공통으로 가지고 있는 약수 중 가장 큰 수

def gcd(a, b):
    # 최대공약수 구하기
    while b > 0:
        a, b = b, a%b
    
    return a

• 예를들어 a = 2, b = 7 이라면
  • a, b = 7, 2%7
    • a = 7, b = 2
  • a, b = 2, 7%2
    • a = 2, b = 1
  • a, b = 1, 2%1
    • a = 1, b = 0

최소공배수: 두 수의 배수 중 공통이 되는 가장 작은 숫자

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

• 두 수를 곱하고 최대공약수로 나눠주면 → 최소공배수