[python] 백준 2609번 최대공약수와 최소공배수

백준 2609번 최대공약수와 최소공배수

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

문제

풀이

시간초과 나는 풀이지만 현명한 for loop 사용법

n,m = map(int, input().split())

# gcd
for i in range(min(n,m), 0, -1):
    if n % i == 0 and m % i == 0:
        print(i)
        break

# lcm
for i in range(max(n,m), (n*m)+1):
    if i % n == 0 and i % m == 0:
        print(i)
        break

최대공약수는 큰 수에서 하나씩 작아지도록 설계하기
최소공배수는 두 수의 곱까지 반복되게 설계하기

유클리드 호제법

n,m = map(int, input().split())

def gcd(n,m):
    while m:
        n,m = m, n%m
    return n

gcd = gcd(n,m)
lcm = n*m // gcd
print(gcd)
print(lcm)

📌 주의

유클리드 호제법 까먹지 말자.
최소공배수 = a * b // 최대공약수