[BOJ] 2609 | 최대 공약수와 최소 공배수

2609 | 최대 공약수와 최소 공배수
https://www.acmicpc.net/problem/2609

내 코드

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

# 최대 공약수
for i in range(min(a,b), 0, -1):
    if a%i == 0 and b%i == 0:
        print(i)
        break

# 최소 공배수
for i in range(max(a,b), a*b+1, max(a,b)):
    if i%a == 0 and i%b == 0:
        print(i)
        break

이상적인 코드

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


def get_lcm(a, b):
    return a * b // get_gcd(a, b)


a, b = map(int, input().split())
print(get_gcd(a, b))
print(get_lcm(a, b))

• 유클리디안 호제법

학습

• a를 b로 나눈 나머지(mod)와 b의 최대공약수(gcd)는 a와 b의 최대공약수(gcd)는 같다

• 최소공배수(lcm)는 두 수의 곱을 최대공약수로 나눈 것