정수론 및 조합론 (최대공약수, 최소공배수, 약수, 팩토리얼 등)

정수론 및 조합론 (최대공약수, 최소공배수, 약수, 팩토리얼 등)

최대공약수 (GCD) - 유클리드 호제법

유클리드 호제법
a % b == 0 이라면 gcd(a, b) = b
a % b != 0 이라면 gcd(a, b) = gcd(a, a%b)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

파이썬 math 함수 이용 시,

math.gcd(a, b)

최소공배수 (LCM)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

a * b 에서 최대공약수로 나눠주기

약수

에라토스테네스의 체