BaekJoon 2609번: 최대공약수와 최소공배수 (Python)

---

1. Problem

---

2. Solution

* Point! 유클리드 호제법 사용

def GCD(a, b):
    while a % b != 0:
        a, b = b, a % b
    return a

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

A, B = map(int, input().split())
print(GCD(A, B))
print(LCM(A, B))

---

3. Detail

• 유클리드 호제법
  유클리드 호제법이란 2개의 자연수 a와 b가 주어졌을 때 a와 b의 최대공약수는 a를 b로 나눈 나머지 값과 b의 최대공약수와 같다는 원리를 활용한 알고리즘이다.
  즉, 2개의 자연수 a와 b가 주어졌을 때 b -> a에 대입하고, a를 b로 나눈 나머지 r -> b에 대입해서 나머지 r이 0이 될 때까지 반복하여 마지막 b 값을 도출하면 두 자연수 a와 b의 최대공약수가 된다.

# example
a = 24, b = 18

a    b    r
24 % 18 = 6
18 %  6 = 0

위의 example을 보면 나머지 r이 0이 될 때까지 반복되고, 마지막 b 값은 6이므로 24와 18의 최대공약수는 6이 되는 것을 알 수 있다. 위 과정을 python code로 작성하면 아래와 같이 된다.

def GCD(a, b):
    while a % b != 0:
        a, b = b, a % b
    return a

a % b(r)가 0이 될 때까지 while문을 통해 반복하고, a % b = r 연산 후에는 b -> a로 a % b -> b로 각각 변경해준다. 그리고 마지막에 변수 a에 저장되는 값인 a와 b의 최대공약수를 return한다.

최소공배수는 최대공약수를 구하는 함수인 GCD(a, b)를 이용하여 쉽게 구할 수 있다. 최소공배수 x 최대공약수 = a * b이므로 식을 변형하면 최소공배수 = (a * b) // GCD(a, b)가 되고, 이를 python code로 작성하면 아래와 같다.

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

GCD(a, b), LCM(a, b) 함수가 물론 간단하긴 하지만 python 내장 라이브러리인 math를 사용하면 아래의 python code처럼 더욱 편하게 사용할 수 있다.

import math

a, b = 15, 25

print(math.gcd(a, b))
print(math.lcm(a, b))

<output>
5
75

---