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

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

2609번: 최대공약수와 최소공배수

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

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


a, b = map(int, input().split())
print(gcd(a, b))
print(lcm(a, b))

 

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

유클리드 호제법 (Euclidean Algorithm)을 사용합니다.

예시: 32와 22의 최대공약수를 구한다고 하면

1. 32%22 = 나머지 10

2. 22%10 = 나머지 2

3. 10%2 = 나머지 0

-> 즉, 나눠지는 마지막 2가 최대공약수입니다.

​

최고공배수 (Least Common Multiple)

a, b의 곱에서 a, b의 최대공약수를 나눠준 것과 같습니다.

 

 

만약 여러 숫자의 최소공배수를 구할 경우:

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

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

def lcm_multiple(arr):
    while True:
        arr.append(lcm(arr.pop(), arr.pop()))
        if len(arr) == 1:
            return arr[0]
        
print(lcm_multiple([2, 4, 5, 10]))
#20

 

1. 2개 수의 최소공배수를 구합니다.

2. 위에서 구한 최소공배수와 아직 계산하지 않은 값 1개를 선택해 최소공배수를 구합니다.

3. 반복해서 모든 수에 대해 최소공배수를 구합니다.