최대공약수(GCD)와 최소공배수(LCM) 알고리즘 이론과 파이썬 구현

최대공약수(GCD)와 최소공배수(LCM) 알고리즘

최대공약수(GCD : Greatest Common Divisor)
최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미합니다.

 

최소공배수(LCM : Least Common Multiple)

최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미합니다.

최소공배수 = 두 자연수의 곱 / 최대공약수

 

유클리드 알고리즘은 자연수 2개의 최대공약수를 구하는 알고리즘입니다.
2개의 자연수 a, b(a > b)에 대해 a를 b로 나눈 나머지를 r(0 < r < b)이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다. 이 알고리즘은 명시적으로 기술된 가장 오래된 알고리즘으로도 알려져 있습니다.

 

유클리드 알고리즘은
1. a, b 두 수가 주어집니다. (a > b)
2. b가 0이면 a을 리턴합니다.
3. a가 b로 나눠 떨어지지 않으면 a를 b로, b를 a에서 b로 나눈 나머지를 대입하고 1번으로 돌아갑니다.
3. a가 b로 나눠 떨어지면 b을 리턴합니다.

 

유클리드 알고리즘을 이용해 54, 20의 최대공약수를 구하는 예시입니다. (%는 나머지 구하기)
54 % 20 = 14
20 % 14 = 6
14 % 6 = 2
6 % 2 = 0

6 % 2가 0이 되기 때문에 최대공약수는 2가 됩니다.

이를 이용해 54*20/2=540를 계산하면 나오면 540이 최소공배수가 됩니다.

 

유클리드 알고리즘을 이용해 54, 24의 최대공약수를 구하는 예시입니다.
54 % 24 = 6
24 % 6 = 0
24 % 6가 0이 되기 때문에 최대공약수는 6이 됩니다.

 

최대공약수(GCD)와 최소공배수(LCM) 알고리즘의 파이썬 코드입니다.

def gcd(a,b): # 최대공약수
    if b == 0:
        return a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

x=54
y=20

# 최대공약수(GCD)
# 출력>>2
print(gcd(x,y))

# 출력>>6
print(gcd(54,24))

# 최소공배수(LCM)
# 출력>>540
print(int(x*y/gcd(x,y)))