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

문제링크

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

문제 풀이

1. 공약수를 직접 구하는 방법

 

• 1부터 두 수 중 작은 수까지 반복하면서 공약수를 구합니다.
• 공약수 중 가장 큰 값을 max(tmp)로 출력합니다. 이것이 최대공약수(GCD)입니다.
• 최대공약수를 이용하여 두 가지 방법으로 최소공배수(LCM)를 계산합니다:
  • 방법 1: GCD * (a // GCD) * (b // GCD)
  • 방법 2: (a * b) // GCD

 

2. 유클리드 호제법 (반복문)

 

• 큰 수를 n, 작은 수를 m으로 설정합니다.
• m이 0이 될 때까지 n을 m으로 나눈 나머지를 반복적으로 계산합니다.
• 나머지가 0이 되면, 마지막 n이 최대공약수(GCD)가 됩니다.
• 최소공배수는 (a * b) // GCD로 계산합니다.

 

3. 유클리드 호제법 (재귀함수)

 

• n % m이 0이 될 때까지 재귀 호출을 합니다.
• 종료 조건으로 m이 0이 되면 n을 반환합니다. 이 n이 최대공약수(GCD)입니다.
• 최소공배수는 동일하게 (a * b) // GCD로 계산합니다.

유클리드 호제법이란?

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

 

4. Python 표준 라이브러리 사용

 

• math.gcd(a, b)를 사용하여 최대공약수를 구합니다.
• math.lcm(a, b)를 사용하여 최소공배수를 구합니다.

 

 

코드

# 공약수를 직접 구하는 방법

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

tmp = []
for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i == 0:
        tmp.append(i)

# 최대공약수 출력
print(max(tmp))

# 최소공배수 출력 방법 1
print(max(tmp) * (a // max(tmp)) * (b // max(tmp)))

# 최소공배수 출력 방법 2
print((a * b) // max(tmp))

# 유클리드 호제법(반복문)
a, b = map(int, input().split())

n, m = max(a, b), min(a, b)

while m > 0:
    n, m = m, n % m

# 최대공약수 출력
print(n)

# 최소공배수 출력
print((a * b) // n)

# 유클리드 호제법 (재귀함수)
def cal(n, m):
    if m == 0:
        return n
    return cal(m, n % m)

a, b = map(int, input().split())
n, m = max(a, b), min(a, b)

# 최대공약수 출력
print(cal(n, m))

# 최소공배수 출력
print((a * b) // cal(n, m))

# Python 표준 라이브러리 사용
import math

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

# 최대공약수 출력
print(math.gcd(a, b))

# 최소공배수 출력
print(math.lcm(a, b))