[수학] 백준 2609번 최대공약수와 최소공배수 with python (유클리드 호제법)

https://www.acmicpc.net/problem/2609

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

for i in range(abs(a-b), 1, -1):
    if a%i == 0 and b%i == 0:
        gcd *= i
        a //= i
        b //= i
lcm = gcd*a*b
print(gcd)
print(lcm)

옛날에 학생때 최대공배수 최대공약수를 구할 때 13, 17같은 한번에 알아차리기 어려운 소수들이 있어서 썻던 방법이 큰 수에서 작은 수를 뺀 차이의 약수로 나누는 수를 결정했던 기억이 있었다. 그냥 내가 그렇게 풀었었다ㅋㅋㅋㅋ
근데 그렇게 풀었는데 틀렸다고 나옴ㅎㅎ 근데 정확히 아직 반례를 찾진 못했다ㅜㅜ
그래서 무슨 방법으로 풀어야 잘 풀었다고 소문이 날까 하고 찾아보던 중 유클리드 호제법을 사용하면 된다는 블로그를 봤다!
유클리드 호제법이란?
두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 r이 0이면 그때 b가 최대공약수
따라서 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수라는 특징이 있다.

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

if a > b:
    big = a
    small = b
else :
    big = b
    small = a

r = big % small

while r != 0:
    big = small
    small = r
    r = big % small
print(small)
print(a * (b//small))

그 특징을 그대로 코드로 옮겼다.

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

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

그리고 굉장히 간단한 코드를 찾았다...ㅎ
이미 파이썬에선 사실 gcd와 lcm 함수를 제공하긴한다.
그래도 이런 원리를 알고 푸니까 신기했던 문제였다!