January 1, 2023

유클리드 호제법

• 두 수의 최대 공약수를 구하는 알고리즘

알고리즘

• 큰 수를 작은 수로 나눈 나머지를 구한다.

  $$ a \% b = d_1 ... r_1 $$

• 나눴던 수와 나머지로 나머지를 구한다.

  $$ b \% r_1 = d_2 ... r_2 $$

• 나머지가 0이 될 때 까지 위의 과정을 반복한다.

• 나머지가 0이 되었을 때, 나누는 수가 최대 공약수이다.

코드

a = 1112
b = 695

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

    return b

def gcd2(a, b):
    return a if b == 0 else gcd2(b, a % b)

print(gcd(a, b))

최소 공배수 (LCM)

$$ {a * b}\over{gcd(a, b)} $$

코드

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

참고 링크

유클리드 호제법(Euclidean-algorithm)

[Algorithm] 코드로 최대공약수(GCD)와 최소공배수(LCM) 구하기