[python] 최소공배수, 최대공약수

최대공약수

1. 유클리드 호제법을 이용하여 최대공약수 구하는 방법

   👉 아래 최소공배수에서 확인

2. for문을 이용하여 두 수 의 최대공약수를 구하는 방법

def gcd(a, b):
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i

3. math 라이브러리 이용하여 최대공약수 구하기

import math

math.gcd(a, b)

최소공배수

1. 최대공약수를 이용하여 최소공배수를 구하는 함수

def gcd(a, b):
    """두 수의 최대공약수를 구하는 함수"""
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    """두 수의 최소공배수를 구하는 함수"""
    # 두 수의 곱을 최대공약수로 나누어주면 최소공배수를 구할 수 있다.
    return (a * b) // gcd(a, b)

2. for문을 이용하여 두 수의 최소공배수를 구하는 함수

def lcm(a, b):
    for i in range(max(a, b), (a * b) + 1):
        if i % a == 0 and i % b == 0:
            return i

3. math 라이브러리를 이용하여 최소공배수 구하기

import math

def lcm_math(a, b):
    gcd_value = math.gcd(a, b) # 최대공약수를 구함
    lcm = (a * b) // gcd_value # 최소공배수를 구함
    return lcm