[Algorithm] GCD / LCM / Euclidean Algorithm

GCD (최대공약수)

Greatest Common Divisor

두 개 이상의 수의 공통된 약수(공약수) 중 가장 큰 값

공약수가 1뿐인 경우,
해당 수들의 관계를 서로소(Coprime) 라고 한다.

두 수의 최대공약수를 구하는 방법

두 수를 각각 a, b 로 가정

해당 포스트에서는 두가지 방법으로 접근하였다.

# 1. 하나씩 전부 해보기

• 반복문을 통해 2부터 제시된 두 수의 작은값 min(a, b)까지 나누기를 모두 시행

• 만약 나누기를 시행한 수가 a, b 모두에서 나머지 0일 경우 해당 수를 변수 gcd 로 할당

• 반복문을 모두 시행한 뒤에 최종적으로 변수 gcd 에 저장되어있는 값이 최대공약수

Python Implementation Code

def GCD(a, b):
    smaller = min(a, b)
    for i in range(1, smaller+1):
        if a % i == 0 and b % i == 0:
            result = i
    return result

# 2. 유클리드 호제법 (Euclidean Algorithm)

두 수 a, b (a > b) 가 있다.

a 나누기 b 의 나머지를 r₁ 라고 정의한다면
(a, b) 의 최대공약수는 (b, r₁) 의 최대공약수와 동일하다.

b 나누기 r₁ 의 나머지를 r₂ 라고 정의한다면
(b, r₁) 의 최대공약수는 (r₁, r₂) 의 최대공약수와 동일하다.

위의 방법을 반복하여 나머지 r_n 이 0이 되었을 때
나누는 수가 최대공약수가 된다.

Example

유클리드 호제법으로 100과 24의 최대공약수 구하기

[100, 24]

100 나누기 24 의 나머지는 4 이다.

[24, 4]

24 나누기 4의 나머지는 0이다.
따라서 최대공약수는 4가 된다.

Python Implementation Code

def euclidean(a, b):
    num, div = max(a, b), min(a, b)
    while num % div:
        num, div = div, num % div
    return div

LCM (최소공배수)

Least Common Multiple

두 개 이상의 수의 공통된 배수 중 가장 작은 값

두 수의 최소공배수를 구하는 방법

두 수를 각각 a, b 로 가정

LCM = a x b / GCD(a, b)

위와 같은 식이 성립한다.

Python Implementation Code

def GCD(a, b):  # Euclidean
    num, div = max(a, b), min(a, b)
    while num % div:
        num, div = div, num % div
    return div
    

def LCM(a, b):
    return a * b / GCD(a, b)