[백준/파이썬] 2609번 최대공약수와 최소공배수 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 2609번 최대공약수와 최소공배수
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

두 자연수의 최대공약수(GCD)와 최소공배수(LCM)를 구하는 문제입니다.

코드

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

def gcd(a, b):
    r = b % a
    if r == 0:
        return a
    else:
        return gcd(r, a)

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

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

설명

유클리드 호제법으로 최대공약수를 구하고, LCM = (a*b) / GCD 공식을 사용해 최소공배수를 계산합니다.

---

• 백준 문제풀이 전체 목록 보기

---