유클리드 호제법과 여러 수의 최소공배수

재귀를 쓰기 시작하면서 남긴 메모가 하나 있다.

재귀는 똑같은 것을 반복하는 것이 아니다. 기본적인 로직만 같을 뿐.

호제법이 그 예다. 같은 함수를 부르지만 인자가 매번 작아진다.

def do(a, b):
    if b == 0:
        return a
    return do(b, a % b)

gcd(a, b) 와 gcd(b, a % b) 의 답이 같다는 게 전부다. a % b 는 반드시 b 보다 작으므로 두 번째 인자가 계속 줄고, 결국 0이 된다. 그때의 첫 번째 인자가 답이다.

최소공배수는 여기서 바로 나온다.

gcd = do(a, b)
lcm = a * b // gcd

세 개 이상일 때

수가 여러 개면 앞에서부터 둘씩 접어 나간다.

def do(a, b):
    if b == 0:
        return a
    return do(b, a % b)

data = [2, 16, 34, 96, 124]
lcm = data[0]
for i in range(len(data) - 1):
    lcm = lcm * data[i + 1] // do(lcm, data[i + 1])

print(f'lcm:{lcm}')

지금까지의 lcm과 다음 수의 lcm을 다시 구하는 걸 반복한다. lcm(a, b, c) = lcm(lcm(a, b), c) 라서 성립한다.

곱하고 나서 나누는 순서로 쓰면 중간값이 커진다. lcm // gcd * next 로 먼저 나누면 그걸 줄일 수 있는데 파이썬은 정수 크기 제한이 없어서 여기서는 그냥 뒀다.