(매일 BOJ) Python 2609번 최대공약수와 최소공배수

📌 문제 설명

두 개의 자연수가 주어질 때, 두 수의 최대공약수(GCD)와 최소공배수(LCM)를 구해서 출력합니다.

• 최대공약수(GCD)는 두 수의 공통된 약수 중에서 가장 큰 수입니다.
• 최소공배수(LCM)는 두 수의 공통된 배수 중에서 가장 작은 수입니다.

---

📥 입력 조건

• 두 개의 자연수가 공백으로 구분되어 한 줄에 주어집니다.
• 입력되는 자연수는 10,000 이하입니다.

---

📤 출력 조건

첫째 줄에 최대공약수, 둘째 줄에 최소공배수를 출력합니다.

---

💡 문제 해결 아이디어

이 문제는 유클리드 알고리즘을 활용하면 쉽게 풀 수 있습니다.

• **최대공약수(GCD)**는 유클리드 알고리즘을 이용해서 빠르게 구할 수 있습니다.
• **최소공배수(LCM)**는 다음과 같은 식을 이용하면 편리하게 구할 수 있습니다.

📌 유클리드 알고리즘이란?

유클리드 알고리즘(Euclidean Algorithm)은 **두 자연수의 최대공약수(GCD)**를 구할 때 사용하는 대표적인 알고리즘입니다.
이는 고대 수학자 유클리드가 제시한 알고리즘으로, 굉장히 빠르고 효율적입니다.

---

📗 알고리즘 원리

유클리드 알고리즘은 다음 성질을 기반으로 합니다.

두 자연수 a와 b(a > b)에 대해,
a를 b로 나눈 나머지를 r이라고 하면:

• GCD(a, b) = GCD(b, r) 이 성립합니다.

이 과정을 반복해서 나머지가 0이 될 때까지 계속 진행합니다.
이때 나머지가 0이 되는 순간의 **나누는 수(제수)**가 두 수의 최대공약수(GCD)가 됩니다.

---

🔍 예시로 살펴보기

예를 들어 두 수 24와 18의 최대공약수는?

Step 1

• 24 ÷ 18 → 몫: 1, 나머지: 6
  → GCD(24, 18) = GCD(18, 6)

Step 2

• 18 ÷ 6 → 몫: 3, 나머지: 0
  → 나머지가 0이므로 멈춥니다.

즉, 최대공약수는 6입니다.

 

def gcd(a,b): #유클리드 알고리즘

    while b:

        a,b = b,a%b

    return a

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

output_1 = gcd(a,b)

output_2 = (a*b)//output_1

print(output_1)

print(output_2)