[파이썬] 백준 2609 최대공약수, 최소공배수

✅ 백준 문제 링크: 백준 2609번 - 최대공약수와 최소공배수

백준 2609 문제

1. 최대공약수(GCD)와 최소공배수(LCM)란?

 

✅ 최대공약수(GCD, Greatest Common Divisor)

 

0이 아닌 두 정수 n과 m이 공통으로 가지고 있는 약수 중 가장 큰 수를 의미한다.

 

약수란?

어떤 수를 나누어 떨어지게 하는 수를 뜻한다.

예를 들어 6의 약수는 1, 2, 3, 6 이다.

즉, 어떤 수를 두 개의 정수로 나눌 수 있으면, 그 정수들은 해당 수의 약수이다.

 

✔ 예제: 12와 20의 최대공약수

12의 약수: 1, 2, 3, 4, 6, 12  
20의 약수: 1, 2, 4, 5, 10, 20  
공통 약수: 1, 2, 4  
최대공약수(GCD) = 4

 

✅ 최소공배수(LCM, Least Common Multiple)

 

두 정수 n과 m의 공통 배수 중 가장 작은 수를 의미한다.

 

✔ 예제: 12와 20의 최소공배수

12의 배수: 12, 24, 36, 48, 60, ...  
20의 배수: 20, 40, 60, 80, ...  
공통 배수: 60, 120, ...  
최소공배수(LCM) = 60

 

2. 파이썬에서 최대공약수와 최소공배수 구하기

 

Python에서는 math 모듈을 사용하여 간단하게 최대공약수와 최소공배수를 구할 수 있다.

 

🔹 math.gcd(n, m)

• 두 수 n과 m의 최대공약수(GCD) 를 반환한다.

• 유클리드 호제법을 기반으로 한 빠른 알고리즘을 사용한다.

 

🔹 math.lcm(n, m) (Python 3.9 이상)

• 두 수 n과 m의 최소공배수(LCM) 를 반환한다.

 

3. 파이썬 코드 (math 모듈 사용)

import math
# 입력 받기
var = input().split(" ")
lcmNum = 0
gcdNum = 0

#math.gcd, math.lcm 함수 이용해서 문제풀이
# 최대공약수(GCD) 계산
gcdNum = math.gcd(int(var[0]), int(var[1])) 
# 최소공배수(LCM) 계산 
lcmNum = math.lcm(int(var[0]), int(var[1])) #Python 3.9 이상에서 사용 가능
print(gcdNum)
print(lcmNum)

 

4. 예제 테스트

 

✔ 입력 예시

24 18

 

✔ 출력 예시

6
72

 

✔ 입력 예시 2

8 28

 

✔ 출력 예시 2

4
56

 

5. math.lcm() 없이 최소공배수 구하기 (Python 3.8 이하 버전)

 

Python 3.8 이하에서는 math.lcm() 함수가 없기 때문에,

다음과 같이 직접 최소공배수를 구할 수 있다.

import math

# 입력 받기
a, b = map(int, input().split())

# 최대공약수(GCD)
gcd_value = math.gcd(a, b)

# 최소공배수(LCM) 공식 적용
lcm_value = (a * b) // gcd_value

# 결과 출력
print(gcd_value)
print(lcm_value)

✔ Python 3.8 이하를 사용하는 경우 위 코드로 최소공배수를 구할 수 있다.

 

6. 정리

 

✔ 최대공약수(GCD): 두 수의 공통된 약수 중 가장 큰 수

✔ 최소공배수(LCM): 두 수의 공통된 배수 중 가장 작은 수

✔ Python에서는 math.gcd()와 math.lcm() 함수를 사용하면 쉽게 구할 수 있음

✔ Python 3.8 이하에서는 (a * b) // gcd(a, b) 공식으로 최소공배수 계산 가능