[백준 2609번] 최대공약수/최소공배수 - 유클리드 호제법

 

- 짠 코드

def gcd(x, y):
    min1 = min([x, y])
    max1 = max([x, y])
    while min1 != 0:
        max1, min1 = min1, max1 % min1
    return max1


# 최소공배수
def lcm(x, y):
    return x * y // gcd(x, y)


a, b = map(int, input().split())

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

# 재귀과정으로 만들면 저절로 큰값이 x, 작은값이 y로 가도록 만들 수 있다.

 

- 최대공약수 : 두가지 수가 주어졌을 때 더이상 공약수가 없을 때까지 공약수로 나눠가며 지금까지 나눈 공약수들을 곱해주면 최대공약수가 된다. 

 

유클리드 호제법 : 두 양의 정수 a,b (a > b)에 대하여 a = bq + r ( 0 <= r < b ) 일 때 a,b의 최대공약수는 b,r의 최대공약수와 같다. -- >  r=0일때 a,b의 최대공약수는 b가 된다.

 

* 알고리즘 사용방법

1. 큰 수, 작은 수 -> 작은 수, 큰 수를 작은 수로 나눈 나머지

2. 작은 수가 0이 될때까지 반복한다.

3. 큰 수를 출력한다.

 

* 알고리즘 이해 ( 증명 )

두 개의 숫자 a, b가 있을 때 두 수는 각각 서로소인 A, B와 최대공약수 G의 곱으로 표현할 수 있다.

a, b = AG, BG 이를 a= bq + r 에 대입하면 AG = BGq + r         -->          G(A-Bq) = r

즉 r = (A-Bq)G, b = (B)G로 귀류법을 사용한 증명을 통해 A-Bq와 B는 서로소임을 증명할 수 있어 a,b의 최대공약수는 b,r의 최대 공약수임을 확인할 수 있다. 

 

- 최소공배수 : a = AG, b = BG일 때 a * b = GGAB임을 일 수 있고 ( A, B는 서로소 ) 여기서 최소 공배수는 GAB이기 때문에 최소 공배수는 a * b에서 최대공약수 G를 나눠서 구할 수 있다.