January 1, 2023

2609번: 최대공약수와 최소공배수

문제 요약

• 두 개의 자연수가 주어졌을 때 최대 공약수와 최대 공배수를 출력
• 1 ≤ 자연수 ≤ 10,000
• 시간 제한 : 1초

풀이

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

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

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

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

• 유클리드 호제법 이용

시간 복잡도

• 입력의 크기에 비례하지 않는다.
• O(1)