백준 2609 파이썬 python : 최대공약수와 최소공배수 @@황소처럼 우직하게@@ [유클리드 호제법 알고리즘][gcd][lcm]

이걸 아직도 파악하지 못하고 있었다니.. 반성한다.

유클리드 호제법은 기원전 300년에 나온 첫번째 알고리즘으로 유명하다.

a 를 b로 나눈 나머지를 r 이라고 했을 때, a와 b의 최대공약수는 b와 r의 최대공약수이다.

다시말해서, a와 b의 최대공약수는 b와 a%b의 최대공약수이다.

재귀가 느껴지는가? 반복이 느껴지는가? a%b 값이 0이 되었을 때, b 값이 최대공약수이다.

최소공배수는 어떻게 구할까?

최대 공약수를 G라고 했을 때,

a = G * x

b= G * y

이다. G가 최대공약수 그 자체이기에, x, y는 서로소이다.

하튼, a * b = G * G * x * y   이다.

그럼 최소공배수는 a * b / G 이다.

놀랍지 않은가?

gcd = greatest common divisior : 최대공약수

lcm = least common multiple : 최소공배수

import sys
input = sys.stdin.readline

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

def gcd_r(a, b):
    return gcd_r(b, a % b) if b else a

def gcd(a, b):
    while b > 0:
        tmp = a % b
        a = b
        b = tmp
    return a

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

print(gcd_r(a, b))
print(lcm(a, b))

gcd_r() 은 재귀로  구현한것이며

gcd() 는 반복문으로 구현한 것이다.